A - A Secret -扩展KMP

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N = 1000005;
int Next[N];
long long ex[N],tong[N]; //即extand[]
char p[N],t[N];
int T;
long long ans;
void pre()   // next[i]: 以第i位置开始的子串 与 T的公共前缀
{
    int lp=strlen(p);
    Next[0]=lp;
    int j=0,k=1;
    while(j+1<lp && p[j]==p[j+1]) j++;
    Next[1]=j;
    for(int i=2; i<lp; i++)
    {
        int P=Next[k]+k-1;
        int L=Next[i-k];
        if(i+L<P+1) Next[i]=L;
        else
        {
            j=max(0,P-i+1);
            while(i+j<lp && p[i+j]==p[j]) j++;  // 枚举(p+1，length) 与(p-k+1,length) 区间比较
            Next[i]=j;
            k=i;
        }
    }
}
void exkmp()
{
    int lp=strlen(p),lt=strlen(t);
    pre();  //next数组初始化
    int j=0,k=0;
    while(j<lt && j<lp && p[j]==t[j]) j++;
    ex[0]=j;
    for(int i=1; i<lt; i++)
    {
        int P=ex[k]+k-1;
        int L=Next[i-k];
        if(i+L<P+1) ex[i]=L;
        else
        {
            j=max(0,P-i+1);
            while(i+j<lt && j<lp && t[i+j]==p[j]) j++;
            ex[i]=j;
            k=i;
        }
    }
}
int main()
{

    scanf("%d",&T);
    while(T--)
    {
        memset(tong,0,sizeof(tong));
        scanf("%s%s",&t,&p);
        int lt=strlen(t);
        int lp=strlen(p);
        reverse(p,p+lp);
        reverse(t,t+lt);
        exkmp();
        ans=0;
        for(int i=0; i<lt; i++)
        tong[ex[i]]++;
        for(int i=lp;i;i--)
        {
            tong[i]=(tong[i]+tong[i+1])%mod;
            ans=(ans+tong[i]*i%mod)%mod;
        }
            printf("%lld\n",ans);

    }
}