扩展KMP的模版-白红宇

扩展KMP的模版

阅读量：4204 次

发布时间：2019-05-26

本文共 1099 字，大约阅读时间需要 3 分钟。

 #include <stdio.h>  
 #include <stdlib.h>  
 #include <string.h>  
 #include <iostream>  
 #include <algorithm>  
 using namespace std;  
 const int maxn=100005;  
 int next[maxn],extand[maxn];  
 char S[maxn],T[maxn];  
 void GetNext(const char *T){  
      int len=strlen(T),a=0;  
      next[0]=len;  
      while(a<len-1 && T[a]==T[a+1]) a++;  
      next[1]=a;  
      a=1;  
      for(int k=2;k<len;k++){  
          int p=a+next[a]-1,L=next[k-a];  
          if( (k-1)+L >= p){  
              int j = (p-k+1)>0 ? (p-k+1) : 0;  
              while(k+j<len && T[k+j]==T[j]) j++;  
              next[k]=j;  
              a=k;  
          }  
          else  
              next[k]=L;  
      }  
 }  
 void GetExtand(const char *S,const char *T){  
      GetNext(T);  
      int slen=strlen(S),tlen=strlen(T),a=0;  
      int MinLen = slen < tlen ? slen : tlen;  
      while(a<MinLen && S[a]==T[a]) a++;  
      extand[0]=a;  
      a=0;  
      for(int k=1;k<slen;k++){  
          int p=a+extand[a]-1, L=next[k-a];  
          if( (k-1)+L >= p){  
              int j= (p-k+1) > 0 ? (p-k+1) : 0;  
              while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;  
              extand[k]=j;  
              a=k;  
          }  
          else  
              extand[k]=L;  
      }  
 }  
 int main(){  
     while(scanf("%s%s",S,T)!=-1){  
          GetExtand(S,T);  
          for(int i=0;i<strlen(T);i++)  
              printf("%d ",next[i]);  
          puts("");  
          for(int i=0;i<strlen(S);i++)  
              printf("%d ",extand[i]);  
          puts("");  
     }  
     return 0;  
 }  