1. 简述
KMP是经典的笔试题目之一。昨天复习了一下，主要有一下几点需要注意。
首先，原理上，利用最长的相等前端距离和后端距离（详见C语言名题精选百则6.4节）。 其次，有两类代码，一类实现fail函数，另一类实现next函数。 · fail数组的含义是，当前元素匹配失败了，那么[开始元素，当前元素]范围内，最长前端的下标。假设最长相等前端后端分别为pat[0]-pat[s],pat[i-s]-pat[i], fail[i]=s。很多情况下，没有最长前端，所以可能有很多-1出现（没有的时候，用-1代替）。在kmp主函数中，如果text[t]!=pat[p]，那么p=fail[p-1]+1。 · next数组的含义是，当前元素匹配失败了，那么[开始元素，当前元素的前一元素]的范围内，最长前端的元素后面那个元素的下标。假设最长相等前端后端分别为pat[0]-pat[s],pat[i-1-s]-pat[i-1], next[i]=s+1。对于next只有next[0]=-1其余，最小的也就是0。在kmp主函数中，如果text[t]!=pat[p]，那么p=next[p] · 区别：fail[i]是[0, i]的最长前后端的前端的最后一个元素。 next[i]是[0, i-1]的最长前后端的前端的最后一个元素后面的那个元素，实际上next[i]就是说当前pat[i]匹配失败了，那么下一个可以匹配的pat下标是多少。next[i]"指的是pat[0]到pat[i-1]的范围内，“最长相等前端后端”的前端的最后一个元素的再往后面的一个元素。假设最长相等前端后端分别为pat[0]-pat[s], pat[i-1-s]-pat[i-1]，next[i]=pat[s+1]。 然后，对于next函数，是可以优化的，对于pat[p] == pat[next[p]]的情况，可以想象，如果text[t]!=pat[p]，那么下一个要取p=next[p]，那么由于前者相等，所以必然还是不等还给往前找next[next[p]]，所以可以要求对于next[0]后面的元素，如果pat[p]=pat[next[p]], 令next[p]=next[next[p]]。这一步优化可以在前面求next[p]的过程中，处理出来，也可以在next求出来后，再来一遍进行优化。 KMP可以说的有很多，理解也有很多，就先到这里了。尤其是实现算法的细节也很多，这个比较晕，当前next函数的实现较多，一遍都是将next的，毕竟能够优化嘛，建议找算法的话，找一些权威一点的，维基百科链接的代码，等等。2. 代码
当然上代码还是上自己写的。不一定对啊，不过通过fail和next都通过一些例子验证了，估计不会错吧。其实要记得话，记next应该就够了，网上fail的实现真的很少，看来我看C名题百则上的代码，走了弯路，不过其中关于最长相等前端后端的说明还是不错的，虽然还能说得更好点吧。。呵呵。实际上，最长相等的前端后端是有一种嵌套的前端后端的含义在，书里面没挑明这一点，所以理解起来不是那么直接。
#include < iostream > using namespace std; // fail 函数：经典KMP // next 函数：经典KMP另一种定义 // next-val 函数：改进KMP，要保证pat[i] != pat[next[i]]， // 可以首先求得next数组，然后，求next-val， // 如果pat[i] != pat[next[i]]，那么next-val[i]=next[i]; // 反之next-val[i]=next-val[next[i]]; 由于这种相等的 void get_fail( const char pat[], int fail[]) { int len = strlen(pat); int i,j; fail[ 0 ] = - 1 ; for (i = 1 ; i < len; i ++ ) { for (j = fail[i - 1 ]; j >= 0 && pat[j + 1 ] != pat[i]; j = fail[j]) ; fail[i] = (j < 0 && pat[j + 1 ] != pat[i]) ? - 1 : j + 1 ; } cout << " fail array: " << endl; for ( int i = 0 ; i < len; i ++ ) { cout << i << " : " << fail[i] << endl; }} int kmp_fail( const char text[], const char pat[]) { int t_length = strlen(text); int p_length = strlen(pat); int t,p; int * fail = new int [t_length]; get_fail(pat, fail); for (t = 0 ,p = 0 ; t < t_length && p < p_length; ) { if (text[t] == pat[p]) // 相等都往后走一步 t ++ ,p ++ ; else if (p > 0 ) // 前面还有可能的元素没比较过 p = fail[p - 1 ] + 1 ; else // 可能的元素都比较过了 t ++ ; } delete []fail; return t < t_length ? (t - p_length): - 1 ;} void get_next( const char pat[], int next[]) { int len = strlen(pat); int i,j; next[ 0 ] = - 1 ; for (i = 1 ; i < len; i ++ ) { for (j = next[i - 1 ]; j >= 0 && pat[i - 1 ] != pat[j]; j = next[j]) ; if (j < 0 || pat[i - 1 ] != pat[j]) next[i] = 0 ; else next[i] = j + 1 ; // if (pat[i]==pat[next[i]]) next[i]=next[next[i]]; } cout << " next array: " << endl; for ( int i = 0 ; i < len; i ++ ) { cout << i << " : " << next[i] << endl; } for ( int i = 0 ; i < len; i ++ ) { if (pat[i] == pat[next[i]]) next[i] = next[next[i]]; } cout << " new next array: " << endl; for ( int i = 0 ; i < len; i ++ ) { cout << i << " : " << next[i] << endl; }} int kmp_next( const char text[], const char pat[]) { int t_length = strlen(text); int p_length = strlen(pat); int t,p; int * next = new int [p_length]; get_next(pat, next); for (t = 0 ,p = 0 ; t < t_length,p < p_length; ) { if (text[t] == pat[p]) t ++ ,p ++ ; else if (next[p] == - 1 ) // 说明此时p=0，而且pat[0]都匹配不了 t ++ ; else p = next[p]; } delete []next; return t < t_length ? (t - p_length): - 1 ; } int main() { const char * text = " aaaddddddddddddddddd " ; // const char *pat = "aaaadd"; // const char *pat = "xyxyyxyxyxx"; const char * pat = " abcabcaa " ; cout << " index: " << kmp_fail(text, pat) << endl; cout << " index: " << kmp_next(text, pat) << endl; system( " PAUSE " ); return 0 ;}
主要说一下测试样例：对于pat="abcabcaa"，答案来自网络，只有next和next-val的正确答案：-1,0,0,0,1,2,3,4和-1,0,0,-1,0,0,-1,4。对于pat="xyxyyxyxyxx" 答案来自书籍，只有fail的正确答案：-1,-1,0,1,-1,0,1,2,3,2,0。
3. 参考 C语言名题精选百则，6.4节。 其中讲了fail函数的实现。其中有fail的测试数据。 数据结构习题与解析（第三版，A级，Page114）。 手算KMP匹配的Next值和Nextval值。 其中有next和next-val的测试数据。 Knuth–Morris–Pratt algorithm 维基百科 没仔细看，不过链接了很多代码实现和讲解的网页，由于代码实现细节被一些中文书先入为主了，这些代码有些看不进去。4. 备注 大致参考就这些了，国内的一些博客上的讲解我就不连接了，不能保证其肯定是对的，反正很多我在不会kmp的时候，是看不太懂，好像有一套理解方式是从自动机那边走，算法导论好像就是先讲了自动机，就接着讲了字符串匹配的kmp，我现在的理解方式就是从最长前端最长后端理解。