转载

KMP算法

看严蔚敏的数据结构看得云里雾里，后来看了其它博客才了解得比较透彻。其实算法的大体思路并不难理解。最原始的字符串匹配算法是将匹配串与模式串对齐，然后从左向右一个个比较，如果失配则模式串向右移动一个单位，这样没有利用前面部分匹配的信息，时间复杂度为O(n*m)。

KMP算法则是利用了部分匹配的信息，并以此来判断失配时向右移动多少，时间复杂度为O(n+m)。设i指向匹配串的当前匹配字符，j指向模式串的当前匹配字符，若失配，则j=next[j]。

因此关键就是求模式串的next数组。严蔚敏的教材是针对从1开始的数组的，而且对next数组的值的意义也没说清楚，所以在那里卡了很久，看了其他人的博客才清楚。

要理解next数组还是比较难的，教材上的思路是这样的：

已知next[0]=-1,next[1]=0，设next[j]=k，若t[j]==t[k]且t[j+1]!=t[k+1]，则next[j+1] =next[j]+1；若t[j]==t[k]且t[j+1]==t[k+1]，则next[j+1] = next[k+1]。若t[j]!=t[k]，可以看成模式串自身匹配问题，将模式向右滑动到next[k]，若还是不匹配，就滑动到next[next[k]]，如果最后还是不匹配则就肯定会滑动到next[0]。所以下面的程序会看到if(j ==-1 ||...)

next数组的取值(设模式串为t[])

next[0]=-1 任何模式串的第一个模式值规定为-1

next[j] = -1 （j>k≥1）若t[j] = t[0]且前k个字符不等于j前面的k个字符，则模式值为-1（这表示第一个字符都无法匹配）

next[j] = k （j>k≥1）t[j]!=t[k]且前k个字符等于j前面的k个字符

next[j] = 0 其它情况。这里有三种情况，一种是对于j>k≥1，前k个字符不等于j前面的k个字符且t[j]!=t[0]，自然需要滑动到第一个字符再开始匹配；一种是对于j>k≥1，前k个字符等于j前面的k个字符且t[j]==t[0]，让它直接滑动到第一个字符(因为next[k]会是0)，能够减少比较次数；还有一种就是next[1]总是为0

代码如下

 inline void get_next(string t, int next[]) {     int i = 0, j = -1;     next[0] = -1;     while (i<t.length())     {//j在每次循环开始都表示next[i]的值，同时也表示需要比较的下一个位置          if (j == -1 || t[i] == t[j])         {              ++i;              ++j;             if (t[i] != t[j])                 next[i] = j;             else                 next[i] = next[j];         }         else j = next[j];     } }

 int KMP(string s, string t) {     int i = 0, j = 0;     int s_len = s.length();     int t_len = t.length();     int *next = new int[t_len + 1];     get_next(t, next);     while (i<s_len && j<t_len)     {         if (j==-1 || s[i] == t[j]) { ++i; ++j; }         else             j = next[j];     }     if (j>=t_len) return i - t_len; //匹配成功     else return -1; }

原文 http://www.cnblogs.com/tonychen-tobeTopCoder/p/5170246.html

正文到此结束