KMP算法

ypwq5767 8年前

来自: http://www.cnblogs.com/tonychen-tobeTopCoder/p/5170246.html

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