深入串的模式匹配算法(普通算法和KMP算法)的详解
更新时间：2020年4月25日 17:46 点击：1966
串的定位操作通常称作串的模式匹配，是各种处理系统中的最重要操作之一。
模式匹配最朴素的算法是回溯法，即模式串跟主串一个字符一个字符的匹配，当模式串中跟主串不匹配时，主串回溯到与模式串匹配开始的下一个位置，模式串回溯到第一个位置，继续匹配。算法的时间复杂度为O（m*n），算法如下：
//朴素的串的模式匹配算法，S为主串，T为模式串，即找S中有没有与T相同的字串
int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替
{
int i=pos, j=0;
while(i <strlen(S) && j <strlen(T))//确保未超出字符串的长度
{
if (S[i] == T[j])
{ ++i; ++j;} //如果相同，则继续向后比较
else
{i = i-j+1; j =0;} //如果不同，就回溯，重新查找
}
if (j == strlen(T))
return i-strlen(T); //若匹配成功，返回S中与T字符串相同开始位置的索引
else return 0; //若匹配不成功，返回0
}
O（m*n）的时间复杂度有点大，于是人们发现了KMP算法，核心思想是：当不匹配发生时，主串不回溯，模式串回溯到“合适”的位置，哪个位置合适，只与模式串有关，所以可以先算出模式串中各个字符，当不匹配发生是，应该回溯到哪个位置。算法整体时间复杂度O(m+m)。
算法如下：
void GetNext(char* T, int *next)
{
int i=1,j=0;
next[1]=0;
while( i < strlen(T) )
{
if (j == 0 || T[i] == T[j])
{
++i; ++j;
next[i] = j;
}
else j = next[j];
}
}
int KMP(char* S, char* T, int pos)
{
int i = pos, j = 1;
while (i)
{
if (S[i] == T[j])
{
++ i; ++ j;
}
else
j = next[j];
}
if (j > strlen(T))
return i-T[0];
else
return 0;
}
求next的操作不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下：
void GetNextEx(char *T, int *next)
{
int i=1,j=0; next[1] = 0;
while(i < strlen(T))
{
if (j == 0 || T[i] == T[j])
{
++i; ++j;
if (T[i] == T[j])
next[i] = next[j]; //减少回退次数
else next[i] = j; //和上面算法一样next[i]=j
}
else j = next[j];
}
}
模式匹配最朴素的算法是回溯法，即模式串跟主串一个字符一个字符的匹配，当模式串中跟主串不匹配时，主串回溯到与模式串匹配开始的下一个位置，模式串回溯到第一个位置，继续匹配。算法的时间复杂度为O（m*n），算法如下：
复制代码 代码如下:
//朴素的串的模式匹配算法，S为主串，T为模式串，即找S中有没有与T相同的字串
int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替
{
int i=pos, j=0;
while(i <strlen(S) && j <strlen(T))//确保未超出字符串的长度
{
if (S[i] == T[j])
{ ++i; ++j;} //如果相同，则继续向后比较
else
{i = i-j+1; j =0;} //如果不同，就回溯，重新查找
}
if (j == strlen(T))
return i-strlen(T); //若匹配成功，返回S中与T字符串相同开始位置的索引
else return 0; //若匹配不成功，返回0
}
O（m*n）的时间复杂度有点大，于是人们发现了KMP算法，核心思想是：当不匹配发生时，主串不回溯，模式串回溯到“合适”的位置，哪个位置合适，只与模式串有关，所以可以先算出模式串中各个字符，当不匹配发生是，应该回溯到哪个位置。算法整体时间复杂度O(m+m)。
算法如下：
复制代码 代码如下:
void GetNext(char* T, int *next)
{
int i=1,j=0;
next[1]=0;
while( i < strlen(T) )
{
if (j == 0 || T[i] == T[j])
{
++i; ++j;
next[i] = j;
}
else j = next[j];
}
}
int KMP(char* S, char* T, int pos)
{
int i = pos, j = 1;
while (i)
{
if (S[i] == T[j])
{
++ i; ++ j;
}
else
j = next[j];
}
if (j > strlen(T))
return i-T[0];
else
return 0;
}
求next的操作不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下：
复制代码 代码如下:
void GetNextEx(char *T, int *next)
{
int i=1,j=0; next[1] = 0;
while(i < strlen(T))
{
if (j == 0 || T[i] == T[j])
{
++i; ++j;
if (T[i] == T[j])
next[i] = next[j]; //减少回退次数
else next[i] = j; //和上面算法一样next[i]=j
}
else j = next[j];
}
}
上一篇: 求数组中最长递增子序列的解决方法
下一篇: ubuntu中打开终端的三种解决方法
相关文章
- 我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。今天我们谈到的是对KMP算法的拓展...2020-04-25
- 这篇文章主要介绍了c++ 实现KMP算法的示例，帮助大家更好的理解和学习c++，感兴趣的朋友可以了解下,希望能给你带来帮助...2021-08-15
- 这篇文章主要介绍了C++ 数据结构之kmp算法中的求Next()函数的算法的相关资料,需要的朋友可以参考下...2020-04-25
- 本篇文章是对快速模式匹配算法(KMP)进行了详细的分析介绍，需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了C语言kmp算法简单示例和实现原理探究,本文用简洁的语言说明KMP算法的原理,并给出了示例,需要的朋友可以参考下...2020-04-25
- 本篇文章是对串的模式匹配算法(普通算法和KMP算法)的应用进行了详细的分析介绍，需要的朋友参考下...2020-04-25
- 这篇文章记录一下串里面的模式匹配，模式匹配，顾名思义就是给定一个被匹配的字符串，然后用一个字符串模式（模型）去匹配上面说的字符串，看后者是否在前者里面出现。常用的有2种算法可以实现，下面我们来具体探讨下...2020-04-25
- 这篇文章主要介绍了KMP算法最浅显理解(小白教程)，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 这篇文章主要介绍了c语言中使用BF-KMP算法，大家参考使用...2020-04-25
- KMP算法即字符串匹配算法,C语言中KMP可以避免指针回溯从而达到高效,接下来就来总结一下C语言中实现KMP算法的实例讲解...2020-04-25
- 相信很多人（包括自己）初识KMP算法的时候始终是丈二和尚摸不着头脑，要么完全不知所云，要么看不懂书上的解释，要么自己觉得好像心里了解KMP算法的意思，却说不出个究竟，所谓知其然不知其所以然是也。...2020-04-25