KMP的next数组求法详解

近几天学习kmp算法,在next数组求解上受苦颇深,看了不少博客,感觉写得都不够清晰,所以想按照自己理解的过程来尝试写一下,也便于以后温习。

关于kmp算法的介绍,网上博文有很多,就不再赘述,推荐一篇kmp算法,个人感觉挺好

这里主要详细讲解next数组的求解。
由于在下不擅作图,有的地方单纯用文字描述不够清晰,还请原谅。
若有什么地方写得不对欢迎批评,以便于在下修正。

kmp算法的精髓就在于next数组,从而达到跳跃式匹配的高效模式
next数组的值是代表着字符串的前缀与后缀相同的最大长度,(不能包括自身)

这里举个例子:

1
2
3
4
5
6
7
8
9
10
模式串t  A B A B A A
下标 0 1 2 3 4 5
next 0 0 1 2 3 1

next[0]代表t[0]~t[0]即"A"的最大前后缀,显然为0.
next[1]代表t[0]~t[1]即"AB"的最大前后缀,为0.
next[2]代表t[0]~t[2]即"ABA"的最大前后缀,即"A",长度为1.
next[3]代表t[0]~t[3]即"ABAB"的最大前后缀,即"AB",长度为2.
next[4]代表t[0]~t[4]即"ABABA"的最大前后缀,即"ABA",长度为3.
next[5]代表t[0]~t[5]即"ABABAA"的最大前后缀,即"A",长度为1.

看到这里,next值代表的意义应该可以明白了。
但next数组怎样用代码去求呢,我们当然不可能挨个去比较前后缀。
仍然是上面那个例子

A B A B A A
初始化,next[0]为0;
t[0] != t[1] next[1]为0;
t[0] == t[2] next[2]为1;

在求next[3]时,比较t[1]和t[3]是否相等?
相等:显然 next[3] = next[2]+1;
不相等:怎么办? 看下面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void makeNext(char s[],int next[])
{
int len = strlen(s);
next[0]=0; //初始化
for(int i=1,k=0;i<len;i++)
{
while(k>0 && s[k]!=s[i]) //这个while是最关键的部分
k=next[k-1];
//等价于 k=next[next[i-1]-1]
//等号右边的k起的只是下标的作用
if(s[k]==s[i])
k++; //相等就+1
next[i]=k; //赋值
}
}

例子说话

A B A B A B A C
0 1 2 3 4 5 6 7
next[6] = 5
即前缀为t[0]~t[4] 后缀为t[2]~t[6]
next[4] = 3
即前缀为t[0]~t[2] 后缀为t[2]~t[4]
我们发现
next[4]的前缀一定是next[6]的前缀
next[4]的后缀也一定是next[6]的后缀
(这是while循环的原理,可以试着举个例子验证一下)

现在我们要求next[7],将t[7]与t[5] ( t[next[6]] )比较,发现不相等
那么可以将t[7]与t[3] (t[ next[next[6]-1] ])比较,如果相等,则next[7] = next[4] +1 ;
不相等就重复此过程,直到t[7]与t[0]比较.

上框内过程其实就是代码中,while循环里的内容,现在回过头去看上面代码应该会顺畅很多。

下面附上kmp完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

using namespace std;

void makeNext(char s[],int next[])
{
int len = strlen(s);
next[0]=0;
for(int i=1,k=0;i<len;i++)
{
while(k>0 && s[k]!=s[i])
k=next[k-1];
if(s[k]==s[i])
k++;
next[i]=k;
}
}

int kmp(char t[],char s[])
{
int len1 = strlen(t);
int len2 = strlen(s);
int next[len2];
makeNext(s,next);
for(int i=0,j=0;i<len1;i++)
{
while(j>0 && t[i]!=s[j])
{
j=next[j-1];
}
if(t[i]==s[j])
j++;
if(j==len2)
return i-j+1;
}
}

int main()
{
char t[]="1234561123458412";
char s[]="611";
cout<<t<<endl;
cout<<s<<endl;
cout<<"下标为"<<kmp(t,s)<<endl;
}
如果本文对你有用,可以请作者喝杯茶~
0%