扩展KMP

刘雅琼论文 http://wenku.baidu.com/view/8e9ebefb0242a8956bece4b3.html

论文讲的非常详细。

给定母串S,子串T，n=strlen(S),m=stlrne(T);extand[i]=S[i...n]与T的最长公共前缀长度，要在线性时间求出所有extand[].

下面是代码

#define maxn 10010
int extand[maxn],next[maxn];
void getnext(char *t)
{
    int i,j,len=strlen(t),k;
    next[0]=len;
    i=0;
    while(i<len-1)
    {
        if(t[i]==t[i+1])
            i++;
        else break;
    }
    next[1]=i;
    int a=1;//a表示之前匹配过程中到达最远位置的i的值
    for(k=2;k<len;k++)
    {
        int p=next[a]+a-1;//p表示之前匹配到达最远的位置
        int l=next[k-a];
        if(k-1+l>=p)//第二种情况 长度超过p
        {

 　　　　　 int j=p-k+1>0?p-k+1:0;

　　　　　　while(k+j<len&&t[k+j]==t[j])//枚举(p+1，length) 与(p-k+1,length) 区间比较 
                j++;
            next[k]=j;
            a=k;
        }
        else //第二种情况
            next[k]=l;
    }
}
void getextand(char *s,char *t)
{
    memset(next,0,sizeof(next));
    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(k=1;k<slen;k++)
    {
        int p=a+extand[a]-1;
        int l=extand[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;
    }
}

扩展kmp求回文子串

http://blog.csdn.net/u013480600/article/details/23041391