字符串模式匹配之KMP算法的next数组详解与C++实现

时间:2023-03-09 15:29:14
字符串模式匹配之KMP算法的next数组详解与C++实现

相信来看next数组如何求解的童鞋已经对KMP算法是怎么回事有了一定的了解,这里就不再赘述,附上一个链接吧:https://www.cnblogs.com/c-cloud/p/3224788.html,里面对KMP算法有详细的讲解,如果你还不了解KMP算法,可以看看~~。

下面就来讲解不容易理解但又很重要的next数组,相信这是你看过的最容易理解的next数组的讲解了(*^_^*)。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

一、首先,next数组是什么?

简单来说,假设我们有一个主串S和一个模式串T,并且想知道S是否包含T,如果包含,那么T第一次出现在S中的首字符在什么位置?有一种暴力求法:当S[i]!=T[j]的时候,j回溯到j=0,而i回溯到i=i-j+1,这种方法简答粗暴,但效率低下,时间复杂度的范围是(最好与最坏情况):O(n+m)~O(n*m),其中,n为主串S的长度,m为模式串T的长度;KMP算法对这种BF算法做了很大的改进,其基本思想是主串S不进行回溯,而是希望某趟在S[i]和T[j]匹配失败后,下标i不回溯,下标j回溯到某个位置K,使得T[K]对准S[i]继续进行比较。显然,关键问题是如何确定位置K。而这里的next数组表示的就是这个K值!需要注意的是,这个K值仅依赖于模式串T本身字符序列的构成,与主串S无关。

二、朴素模式匹配算法BF

这里给出BF代码,很简单,就不做具体说明了。

int BF(string S, string T)
{
int i = ; // S 的下标
int j = ; // T的下标
int s_len = S.size(); // 字符串长度
int t_len = T.size();
if(s_len<t_len)
return -;
while (i < s_len && j < t_len)
{
if (S[i] == t[j]) // 相等,则都前进一步
{
i++;
j++;
}
else // 回溯
{
i = i - j + ;
j = ;
}
} if (j == t_len) // 匹配成功
return i - j; return -;
}

时间复杂度的范围是(最好与最坏情况):O(n+m)~O(n*m),其中,n为主串S的长度,m为模式串T的长度。

三、改进的模式匹配算法KMP

KMP算法的核心是如何求出next数组!next数组其实就是查找T中每一位前面的子串的前后缀有多少位匹配,从而决定j失配时应该回退到哪个位置(前后缀的概念请看附录)。

文字总是枯燥的,如果图文并茂,那就更好了!好了,上图!

字符串模式匹配之KMP算法的next数组详解与C++实现

这个图画的就是T这个要查找的关键字字符串。假设我们有一个空的next数组,我们的工作就是要在这个next数组中填值。
下面我们用数学归纳法来解决这个填值的问题。
这里我们借鉴数学归纳法的三个步骤(或者说是动态规划?):
1、初始状态
2、假设第j位以及第j位之前的我们都填完了
3、推论第j+1位该怎么填

初始状态我们稍后再说,我们这里直接假设第j位以及第j位之前的我们都填完了。也就是说,从上图来看,我们有如下已知条件:
next[j] == k;
next[k] == 绿色色块所在的索引;
next[绿色色块所在的索引] == 黄色色块所在的索引;
我们来看下面一个图,可以得到更多的信息:

字符串模式匹配之KMP算法的next数组详解与C++实现

1.由"next[j] == k;"这个条件,我们可以得到A1子串 == A2子串(根据next数组的定义,前后缀那个)。

2.由"next[k] == 绿色色块所在的索引;"这个条件,我们可以得到B1子串 == B2子串。

3.由"next[绿色色块所在的索引] == 黄色色块所在的索引;"这个条件,我们可以得到C1子串 == C2子串。

4.由1和2(A1 == A2,B1 == B2)可以得到B1 == B2 == B3。

5.由2和3(B1 == B2, C1 == C2)可以得到C1 == C2 == C3。

6.B2 == B3可以得到C3 == C4 == C1 == C2

接下来,我们开始用上面得到的条件来推导如果第j+1位失配时,我们应该填写next[j+1]为多少?

next[j+1]即是找T从0到j这个子串的最大前后缀:

#:(#:在这里是个标记,后面会用)我们已知A1 == A2,那么A1和A2分别往后增加一个字符后是否还相等呢?我们得分情况讨论:

(1)如果T[k] == T[j],很明显,我们的next[j+1]就直接等于k+1。用代码来写就是next[++j] = ++k;

(2)如果T[k] != T[j],那么我们只能从已知的,除了A1,A2之外,最长的B1,B3这个前后缀来做文章了。

那么B1和B3分别往后增加一个字符后是否还相等呢?

由于next[k] == 绿色色块所在的索引,我们先让k = next[k],把k挪到绿色色块的位置,这样我们就可以递归调用"#:"标记处的逻辑了。

由于j+1位之前的next数组我们都是假设已经求出来了的,因此,上面这个递归总会结束,从而得到next[j+1]的值。

我们唯一欠缺的就是初始条件了:next[0] = -1,  k = -1, j = 0另外有个特殊情况是k为-1时,不能继续递归了,此时next[j+1]应该等于0,即把j回退到首位。

即 next[j+1] = 0; 也可以写成next[++j] = ++k;

接下来就是代码实现next数组(C++版):

 int* getNext(string T)
{
int T_len = T.size();
int* next = new int[T_len]; // 声明next数组
int i = ; // T的下标
int j = -;
next[] = -;
while (i < T_len)
{
if (j == - || T[i] == T[j])
{
next[++i] = ++j;
}
else
j = next[j];
}
return next; }

KMP优化:

如果T[k] == T[j],很明显,我们的next[j+1]就直接等于k+1。用代码来写就是next[++j] = ++k;可是我们知道,第j+1位是失配了的,如果我们回退j后,发现新的j(也就是此时的++k那位)跟回退之前的j也相等的话,必然也是失配。所以还得继续往前回退。

 int* getNext(string T)
{
int T_len = T.size();
int* next = new int[T.size()]; // 声明next数组
int i = ; // T的下标
int j = -;
next[] = -;
while (i < T_len)
{
if (j == - || T[i] == T[j])
{
if (T[i + ] == T[j + ]) //KMP优化
next[++i] = next[++j];
else
next[++i] = ++j;
}
else
j = next[j];
}
return next; }

完整代码C++:

 #include <iostream>
#include <string>
using namespace std;
//获取next数组
int* getNext(string T)
{
int* next = new int[T.size()]; // 声明next数组
int T_len = T.size();
int i = ; // T的下标
int j = -;
next[] = -;
while (i < T_len)
{
if (j == - || T[i] == T[j])
{
if (T[i + ] == T[j + ]) //KMP优化
next[++i] = next[++j];
else
next[++i] = ++j;
}
else
j = next[j];
}
return next; } // KMP算法,在 S 中找到 T 第一次出现的位置
int KMP(string S, string T) // S为主串,T为模式串
{
int* next = getNext(T);
int i = ; // S下标
int j = ; // T下标
int s_len = S.size();
int t_len = T.size();
while (i < s_len && j < t_len)
{
if (j == - || S[i] == T[j]) //T 的第一个字符不匹配或S[i] == T[j]
{
i++;
j++;
}
else
j = next[j]; // 当前字符匹配失败,进行跳转
}
if (j == t_len) // 匹配成功
return i - j;
return -;
} int main()
{
string S = "bbc abcdab abcdabcdabde";
string T = "abcdabd";
int num = KMP(S, T);
cout << num<<endl;
system("pause");
return ;
}

附录:关于前后缀

来一张图片说明吧:

字符串模式匹配之KMP算法的next数组详解与C++实现

由上图所得, "前缀" 指除了自身以外,一个字符串的全部头部组合;"后缀" 指除了自身以外,一个字符串的全部尾部组合。

参考文献:

[1]王红梅, 胡明, 王涛. 数据结构(C++版)[M]. 北京:清华大学出版社, 2011:83-85.

[2]唐小喵的博客:http://www.cnblogs.com/tangzhengyue/p/4315393.html#3831240