KMP算法的理解

参考:

https://www.zhihu.com/question/21923021/answer/281346746 @海纳 大大讲解得十分清楚,就不重复造轮子了

https://www.cnblogs.com/cherryljr/p/6519748.html 这里的nextval讲的清楚,但是前面太罗嗦,建议跳转nextval挑着看

还借鉴了一点《大话数据结构》,但是它太罗嗦,没看下去的兴趣和耐心,而且和我的next数组定义上有点出入……

要点

  • PMT(Partial Match Table)数组,储存前缀后缀交集最长的长度
  • next数组即PMT数组右移一位,是为了编程方便,next[j] = PMT[j-1]
  • next数组的求值,用pattern串和pattern串匹配求得会方便很多

实现

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<cstring>

const int MAX_N = 1e5;
const int MAX_M = 1e2;

char strt[MAX_N]; //text串
char strp[MAX_M]; //pattern串
int next[MAX_M+2]; //next数组

void getnext()
{
next[0] = -1;
int i = 0;
int j = -1;
int len = strlen(strp);

while(i < len) //注意这里是pattern串和自己匹配求next
{
if(j == -1 || strp[i] == strp[j]) //如果相等,由上一条注释,所以是strp[i] == strp[j]
{
++i;
++j;
next[i] = j;
}
else //回退
j = next[j]; //放心使用next,因为next[j]是上一个j得到的值,即PMT[j-1]是已知的;
}
}

int kmp() //返回匹配的串首在text串中的位置
{
int i = 0;
int j = 0;

int len1 = strlen(strt);
int len2 = strlen(strp);

while(i < len1 && j < len2)
{
if(j == -1 || strt[i] == strp[j])
{
i++;
j++;
}
else
j = next[j];
}
if(j == len2) //如果完全匹配,返回起点在数组中的下标
return i - j;
else //否则返回-1(error)
return -1;
}

int main()
{
scanf("%s", strt);
scanf("%s", strp);
getnext();
int ans = kmp();
printf("%d\n", ans);
return 0;
}

改进

  • nextval数组的建立
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
text = "aaaabcde"
pattern = "aaaaax"
next[] = -1, 0, 1, 2, 3, 4, 0
NO1.
aaaabcde
aaaaa
NO2.
aaaabcde
aaaa
NO3.
aaaabcde
aaa
……
可以看出,因为存在重复的连续序列,所以存在重复匹配
我们希望的是
NO1.
aaaabcde
aaaaa
NO2.
aaaabcde
a

于是改进后的next数组即nextval数组来了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void get_nextval()
{
nextval[0] = -1;
int i = 0;
int j = -1;
int len = strlen(strp);

while(i < len)
{
if(j == -1 || strp[i] == strp[j])
{
++i;
++j;
if(strp[i] != strp[j]) //若不等则正常回退
nextval[i] = j;
else
nextval[i] = nextval[j]; //若相等则回退到j匹配失败时回退的值*(下面解释这一句)
}
else //回退
j = nextval[j];
}
}

上面*注释的解释

例如ababzababx和ababx匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
NO1.
ababzababx
ababx
NO2.
ababzababx
aba
NO3.
ababzababx
a
可以看出,NO1先回退到next[j]再回退到next[next[j]];
所以把next[next[j]]赋值给next[i]即可以一步到位
区分以下两行
next[i] = j; //回退到匹配失败的点
nextval[i] = nextval[j]; //回退到匹配成功的点的回退值
为什么没有nextval[i] = nextval[nextval[j]]呢?
因为是从前往后一步步推过来的,每一步的nextval[i]都是i点匹配失败时回退到的最优点(动态规划思想)

优化后的匹配过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
		a  a  a  a  a  x
next -1 0 1 2 3 4
nextval -1 0 0 0 0 4

NO1.
aaaabcde
aaaaa
NO2.
aaaabcde
a

a b a b a a a b a
next -1 0 1 2 3 1 1 2 3
nextval -1 0 1 0 1 0 0 0

结尾

至此,kmp算法和kmp算法的优化已经完成

真是不容易……

又该补题了