hdu6153

题解：

EX_KMP

先计算出ex数组

然后ans统计前缀

然后乘一下就好了

代码:

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=,M=1e9+;

int n,sum[N],m,nxt[N],match[N],exnxt[N],exmatch[N];

int L[N],R[N];

char s1[N],s2[N],s[N];

void EXKMP(char s[],char t[],int n,int m)

{

    exnxt[]=m;

    for (int i=,po=;t[i];i++)

     {

        int P=po+exnxt[po];

        exnxt[i]=max(min(exnxt[i-po],P-i),);

        while (i+exnxt[i]<m&&t[exnxt[i]]==t[i+exnxt[i]])exnxt[i]++;

        if (i+exnxt[i]>P) po=i;

     }

    for (int i=,po=;s[i];i++)

     {

        int P=po+exmatch[po];

        exmatch[i]=max(min(exnxt[i-po],P-i),);

        while (exmatch[i]<m&&i+exmatch[i]<n&&t[exmatch[i]]==s[i+exmatch[i]])exmatch[i]++;

        if (i+exmatch[i]>P) po=i;

     }

}

int main()

{

    int T;

    scanf("%d",&T);

    while (T--)

     {

         memset(exnxt,,sizeof exnxt);

         memset(exmatch,,sizeof exmatch);

         memset(sum,,sizeof sum);

         memset(s2,,sizeof s2);

         memset(s1,,sizeof s1);

         scanf("%s",&s);n=strlen(s);

         for (int i=;i<n;i++)s1[i]=s[n-i-];

         s1[n]='\0';

         scanf("%s",&s);m=strlen(s);

         for (int i=;i<m;i++)s2[i]=s[m-i-];

         s2[n]='\0';

         EXKMP(s1,s2,n,m);

         for (int i=;s1[i];i++)sum[exmatch[i]]++;

         for (int i=m;i>;i--)sum[i]+=sum[i+];

         long long ans=;

         for (int i=n;i>;i--)(ans+=((long long)i*sum[i]%M))%=M;

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

    }

    return ;

}