KMP算法

发表于 分类于 阅读次数： 本文字数： 390 阅读时长 ≈ 1 分钟

前言

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，
前缀为a、ab，后缀为ba、a
有相同的a，长度为1，赋2

1
2
3
   ↓
ababbaaba
0112

4、下标移到5号位，对应下标为b，
前缀为a、ab、aba，后缀为bab、ab、b
有相同的ab，长度为2，赋3

1
2
3
    ↓
ababbaaba
01123

5、下标移到6号位，对应下标为a，
前缀为a、ab、aba、abab，后缀为babb、abb、bb、b
没有相同的，赋1

1
2
3
     ↓
ababbaaba
011231

6、下标移到7号位，对应下标为a，
前缀为a、ab、aba、abab、ababb，后缀为babba、abba、bba、ba、a
有相同的a，长度为1，赋2

1
2
3
      ↓
ababbaaba
0112312

7、下标移到8号位，对应下标为b，
前缀为a、ab、aba、abab、ababb、ababba，后缀为babbaa、abbaa、bbaa、baa、aa、a
有相同的a，长度为1，赋2

1
2
3
       ↓
ababbaaba
01123122

8、下标移到9号位，对应下标为a，
前缀为a、ab、aba、abab、ababb、ababba、ababbaa，后缀为babbaab、abbaab、bbaab、baab、aab、ab、b
有相同的ab，长度为2，赋3

1
2
3
        ↓
ababbaaba
011231223