hdu6153

题解：

EX_KMP

先计算出ex数组

然后ans统计前缀

然后乘一下就好了

代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000005,M=1e9+7;
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[0]=m;
    for (int i=1,po=1;t[i];i++)
     {
        int P=po+exnxt[po];
        exnxt[i]=max(min(exnxt[i-po],P-i),0);
        while (i+exnxt[i]<m&&t[exnxt[i]]==t[i+exnxt[i]])exnxt[i]++;
        if (i+exnxt[i]>P) po=i;
     }
    for (int i=0,po=0;s[i];i++)
     {
        int P=po+exmatch[po];
        exmatch[i]=max(min(exnxt[i-po],P-i),0);
        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,0,sizeof exnxt);
         memset(exmatch,0,sizeof exmatch);
         memset(sum,0,sizeof sum);
         memset(s2,0,sizeof s2);
         memset(s1,0,sizeof s1);
         scanf("%s",&s);n=strlen(s);
         for (int i=0;i<n;i++)s1[i]=s[n-i-1];
         s1[n]='';
         scanf("%s",&s);m=strlen(s);
         for (int i=0;i<m;i++)s2[i]=s[m-i-1];
         s2[n]='';
         EXKMP(s1,s2,n,m);
         for (int i=0;s1[i];i++)sum[exmatch[i]]++;
         for (int i=m;i>0;i--)sum[i]+=sum[i+1];
         long long ans=0;
         for (int i=n;i>0;i--)(ans+=((long long)i*sum[i]%M))%=M;
         printf("%lld
",ans); 
    }
    return 0;
}