简单比较下KMP,扩展KMP和最小表示法

KMP,扩展KMP和最小表示法都是那种朴素是O(m*n)的优化成O(m+n),而且基本思想都是利用前面已经得到的结果来优化后面的步骤,也就是每当失配时指针会大幅度移动,这样最后达到线性的复杂度。

以S为主串,T为模式串来举例(即用T去匹配S),A表示T匹配T得到的数组,B表示T匹配S得到的数组,然后KMP就是

  1. int j=0;
  2. for(int i=0;i=0;i<n){
  3. while(j>0&&(T[j+1]!=S[i]))j=A[j];
  4.  if(T[j+1]==S[i])
  5.  j++;
  6.  B[i]=j;
  7.  if(j==m-1){
  8.  printf("find!\n");
  9.  j=A[j];
  10.  }
  11. }

这是说如果失配,主串不动,模式串移动到合适位置,而最后B[i]得到的就是S串中以i结尾的能匹配模式串的长度,同理A的求法就是自己匹配自己。

再来看看扩展KMP

  1. j=0;
  2. while(j<strlen(S)&&j<strlen(T)&&T[0+j]==S[0+j])
  3.  j=j+1;
  4. B[0]=j,k=0;
  5. for(int i=1;i<strlen(S);i++){
  6.  int Len=k+B[k]-1,L=A[i-k];
  7.  if(L<Len-i+1)
  8.  B[i]=L;
  9.  else{
  10.  j=max(0,Len-i+1);
  11.  while(i+j<strlen(S)&&j<strlen(T)&&S[i+j]==T[0+j])
  12.  j=j+1;
  13.  B[i]=j,k=i;
  14.  }
  15. }

这里的B[i]得到的则是S串中以i开头的能匹配模式串的长度,综合一下,就是说KMP得到的是S[i-B[i]+1]..S[i]=T[0]..T[B[i]-1],而扩展KMP则是说S[i]..S[i+B[i]-1]=T[0]..T[B[i]-1],这样差别就比较明显了,然后就是每次求后面的都是利用了之前求出的内容来推出后面的,具体还是不明白的话可以查看matrix67大牛的KMP讲解我以前写的扩展KMP的内容,还有就是KMP只是单模式串匹配如果多模式串匹配那就是Aho_Corasick自动机了,其实思想还是KMP的思想,一开始的那张图就是Aho_Corasick自动机构造好图的样式了。

然后就是说一下最小表示法又称作最小环排列,是说把一个字符串看成一个环,有n种线性表示(就是说把环切开) ,这里面最小的就是最小环排列,代码

  1. int MCP(){
  2.     int i = 0, j = 1, count = 0, t,len=n;
  3.     while (i < len && j < len && count < len){      
  4.         tt++;        
  5.         int x = i + count;        
  6.         int y = j + count;        
  7.         if (x >= len) x -= len;        
  8.         if (y >= len) y -= len;
  9.         if (s[x] == s[y])
  10.             count++;
  11.         else{
  12.             if (s[x] > s[y])
  13.                 i = i + count + 1;
  14.             else
  15.                 j = j + count + 1;
  16.             count = 0;
  17.         }
  18.         if(j==i)
  19.          j=i+1;
  20.     }
  21.     return i;                  
  22. }

算法很奇妙,只要失配便大幅度移动指针。正确性需要仔细考虑一下,注意到最小的首字母肯定是最小的,这样后面的也就好想了。
这几个算法如果想明白了,理解还是不难的,而且触类旁通,比如最小回文子串的问题同样可以利用这种用以前的推以后的思想然后得出线性的算法。最后这里有个各种字符串算法的大总结,有兴趣的可以看看。

您可能喜欢:
我猜您可能还喜欢:
, ,

《简单比较下KMP,扩展KMP和最小表示法》有 12 条评论

  1. orbbyrp | #2

    连到网易的连接有问题啊……

  2. IGNORE | #3

    第一个KMP算法的程序里这句话“2.for(int i=0;i=0;i<n){”有问题吧?是不是应该是
    “2.for(int i=0;i<n;i++){”?

  3. Sigma | #4

    strlen一次是On的吧。

Trackbacks/Pingbacks:

  1. 扩展KMP算法(Extend KMP) | IT好站 – 为web开发而生,让网站开发更简单。

发表评论