0%

KMP算法

前言

KMP是一种字符串匹配算法,并不算高效,晦涩难懂,比它简单易懂高效的算法是有,但不知为何,课本只讲了这种字符串匹配算法。
整个算法的精髓就在于next数组的计算,网上关于KMP的资料有很多。这里只讲next数组的计算。

求P={ababbaaba}的next数组

1、首先,给前两个赋值01

1
2
ababbaaba
01

2、下标移到3号位,对应下标为a,
前缀为a,后缀为b,没有相同的,赋1

1
2
3

ababbaaba
011

3、下标移到4号位,对应下标为b,
前缀为aab,后缀为baa
有相同的a,长度为1,赋2

1
2
3

ababbaaba
0112

4、下标移到5号位,对应下标为b,
前缀为aababa,后缀为bababb
有相同的ab,长度为2,赋3

1
2
3

ababbaaba
01123

5、下标移到6号位,对应下标为a,
前缀为aababaabab,后缀为babbabbbbb
没有相同的,赋1

1
2
3

ababbaaba
011231

6、下标移到7号位,对应下标为a,
前缀为aababaababababb,后缀为babbaabbabbabaa
有相同的a,长度为1,赋2

1
2
3

ababbaaba
0112312

7、下标移到8号位,对应下标为b,
前缀为aababaababababbababba,后缀为babbaaabbaabbaabaaaaa
有相同的a,长度为1,赋2

1
2
3

ababbaaba
01123122

8、下标移到9号位,对应下标为a,
前缀为aababaababababbababbaababbaa,后缀为babbaababbaabbbaabbaabaababb
有相同的ab,长度为2,赋3

1
2
3

ababbaaba
011231223
点击进入云乞讨模式!