扩展KMP的模版

记录模版，以后好好学习

#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;
}

扩展KMP的模版

原文：http://blog.csdn.net/dan__ge/article/details/50969881