字符串匹配算法 KMP学习心得

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和

J.H.Morris同时发现，因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。

这周的数据结构课讲的是串，本以为老师会讲解KMP算法的，谁知到他直接略过了...没办法只能自己研究，这一琢磨就是3天，期间我都有点怀疑自己的智商...不过还好昨天半夜终于想明白了个中缘由，总结一些我认为有助于理解的关键点好了...

书上有的东西我就不说了，那些东西网上一搜一大片，我主要说一下我理解的由前缀函数生成的next数组的含义，先贴出求next数组的方法。 1 void GetNext(char* t, int* next) 2 {

3 int i, j, len; 4 i = 0; 5 j = -1;

6 next[0] = -1;

7 while(t[i] != '\\0') 8 {

9 if (j == -1 || t[i] == t[j]) 10 { 11 i++; 12 j++; 13 next[i] = j; 14 } 15 else 16 { 17 j = next[j]; 18 } 19 } 20 }

当一个字符串以0为起始下标时，next[i]可以描述为\"不为自身的最大首尾重复子串长度\"。

也就是说，从模式串T[0...i-1]的第一个字符开始截取一段长度为m(m < i-1)子串，再截取模式串T[0...i-1]的最后m个字符作为子串，如果这两个子串相等，则该串就是一个首尾重复子串。我们的目的就是要找出这个最大的m值。 例如:

若 i = 4 ，则 i - 1 = 3 ， m = next[4] = 2 从T[0...3]截取长度为2的子串，为\"ab\" 从T[0..3]截取最后2个字符，为\"ab\"

此时2个子串相等，则说明 next[4] = 2 成立，也可证明 m = 2 为最大的m值。

本来一开始我是没有加\"不为自身\"这个限制条件的，可是后来我发现一种情况:

若 i = 4 ，则 i - 1 = 3 ， m = next[4] = 3 从T[0...3]截取长度为3的子串，为\"aaa\" 从T[0..3]截取最后3个字符，为\"aaa\"

此时2个子串相等，则说明 next[4] = 3 成立。 但是我发现如果next[4] = 4：

从T[0...3]截取长度为4的子串，为\"aaaa\" 从T[0..3]截取最后4个字符，为\"aaaa\"

此时2个子串也是相等的，那么是不是说明 next[4] 应该等于4呢？

仔细观察后发现，如果 next[4] = 4 ，那么T[0...3]的前4个字符和后4个字符是重合的，并且重复子串和T[0...3]也是相等的。看过教材后发现教材中给出的前缀函数定义有一句 为：next[j] = max{k | 0 < k < j 且 'p[0]...p[k-1]' = 'p[j-k+1]...p[j-1]'}，应该不包含子串为本身的情况...

这样再做PKU 2406 和 PKU 1961 的时候就很简单了，用 length - next[length] 求出\"不为自身的最大首尾重复子串长度\"，此时需要多求一位next[length]值，若最大重复子串的长度是length的非1整数倍，则证明字符串具有周期重复性质。

PKU 2752 是求 前缀 == 后缀 的长度，也就是首尾重复子串长度，利用next数组记录的\"不为自身的最大首尾重复子串长度\"可以马上得到结果。 恩，先说这么多吧，可能有不对的地方，以后理解的更深了再回来改...哪位大牛路过看到错误请指出哈。