UVA5876 Writings on the Wall 扩展KMP

扩展KMP的简单题。

#include<stdio.h>

#include<string.h>

#define maxn 51010

char s[maxn],t[maxn];

int extand[maxn],next[maxn];

void getnext(char *t)

{

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

    next[]=len;

    i=;

    while(i<len-&&t[i]==t[i+])

    {

        i++;

    }

    next[]=i;

    int a=;

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

    {

        int p=next[a]+a-;

        int l=next[k-a];

        if(k-+l>=p)

        {

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

            while(k+j<len&&t[k+j]==t[j])

                j++;

            next[k]=j;

            a=k;

        }

        else next[k]=l;

    }

}

void ekmp(char *s,char *t)

{

    int i,j,slen=strlen(s),tlen=strlen(t),k;

    getnext(t);

    int minlen=slen<tlen?slen:tlen;

    int a=;

    while(a<minlen&&s[a]==t[a])    a++;

    extand[]=a;

    a=;

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

    {

        int p=a+extand[a]-;

        int l=next[k-a];

        if(k-+l>=p)

        {

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

            while(k+j<slen&&j<tlen&&s[k+j]==t[j])

                j++;

            extand[k]=j;

            a=k;

        }

        else extand[k]=l;

    }

}

int main()

{

    int i,j,tt;

    scanf("%d",&tt);

    while(tt--)

    {

        scanf("%s %s",s,t);

        ekmp(s,t);

        int len=strlen(s);

        int ans=;

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

        {

            //printf("%d %d\n",extand[i],len-i);

            if(extand[i]>=len-i)

                ans++;

        }

        printf("%d\n",ans+);

    }

}