#define maxn 10010

int extand[maxn],next[maxn];

void getnext(char *t)

{

    int i,j,len=strlen(t),k;

    next[]=len;

    i=;

    while(i<len-)

    {

        if(t[i]==t[i+])

            i++;

        else break;

    }

    next[]=i;

    int a=;//a表示之前匹配过程中到达最远位置的i的值

    for(k=;k<len;k++)

    {

        int p=next[a]+a-;//p表示之前匹配到达最远的位置

        int l=next[k-a];

        if(k-+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,,sizeof(next));

    getnext(t);

    int slen=strlen(s),tlen=strlen(t),a=;

    int minlen=slen<tlen?slen:tlen;

    while(a<minlen&&s[a]==t[a])a++;//第一个值

    extand[]=a;

    a=;

    for(k=;k<slen;k++)

    {

        int p=a+extand[a]-;

        int l=extand[k-a];

        if(k-+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;

    }

}