ZOJ 3587 扩展KMP

思路：这题确实大帝做得非常机智！字符串先求最长前缀，反的字符串再求一次最长前缀。然后就能够搞了。

每一个子串出现的次数就是最长前缀的次数嘛！

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<queue>

#include<set>

#include<cmath>

#include<bitset>

#define mem(a,b) memset(a,b,sizeof(a))

#define lson i<<1,l,mid

#define rson i<<1|1,mid+1,r

#define llson j<<1,l,mid

#define rrson j<<1|1,mid+1,r

#define INF 0x7fffffff

#define maxn 100005

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

void EKMP(char *s,char *t,ll *next,ll *extend)//s[]为主串，t[]为模版串

{

    int i,j,p,l;

    int len=strlen(t);

    int len1=strlen(s);

    memset(next,0,sizeof(next));

    memset(extend,0,sizeof(extend));

    next[0]=len;

    j=0;

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

    next[1]=j;

    int a=1;

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

    {

        p=next[a]+a-1;

        l=next[i-a];

        if(i+l<p+1)next[i]=l;

        else

        {

            j=max(0,p-i+1);

            while(i+j<len&&t[i+j]==t[0+j])j++;

            next[i]=j;

            a=i;

        }

    }

    j=0;

    while(j<len1&&j<len&&s[j]==t[j])j++;

    extend[0]=j;

    a=0;

    for(i=1; i<len1; i++)

    {

        p=extend[a]+a-1;

        l=next[i-a];

        if(l+i<p+1)extend[i]=next[i-a];

        else

        {

            j=max(0,p-i+1);

            while(i+j<len1&&j<len&&s[i+j]==t[j])j++;

            extend[i]=j;

            a=i;

        }

    }

}

char S[maxn],T[maxn];

ll next[maxn],extend[maxn],sum[maxn],sum1[maxn];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        mem(sum,0);mem(sum1,0);

        scanf("%s%s",S,T);

        EKMP(S,T,next,extend);

        int len1=strlen(S),len2=strlen(T);

        for(int i=0;i<len1;i++)

            sum[extend[i]]++;

        for(int i=len2-1;i>=1;i--)

            sum[i]+=sum[i+1];

        reverse(S,S+len1);

        reverse(T,T+len2);

        EKMP(S,T,next,extend);

        for(int i=0;i<len1;i++)

            sum1[extend[i]]++;

        for(int i=len2-1;i>=1;i--)

            sum1[i]+=sum1[i+1];

        ll ans=0;

        for(int i=1;i<len2;i++)

            ans+=sum[i]*sum1[len2-i];

        printf("%lld\n",ans);

    }

    return 0;

}

/*

2

aaabbb

ab

ababaabaaaab

abaab

*/