HDU - 6153 A Secret （KMP）

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<queue>
    #include<bitset>
    #include<map>
    #include<unordered_map>
    #include<set>
    #define ui unsigned int
    #define ll long long
    #define llu unsigned ll
    #define ld long double
    #define pr make_pair
    #define pb push_back
    #define lc (cnt<<1)
    #define rc (cnt<<1|1)
    #define len(x)  (t[(x)].r-t[(x)].l+1)
    #define tmid ((l+r)>>1)
    #define fhead(x) for(int i=head[(x)];i;i=nt[i])
    //#define max(x,y) ((x)>(y)?(x):(y))
    //#define min(x,y) ((x)>(y)?(y):(x))
    using namespace std;
    
    const int inf=0x3f3f3f3f;
    const ll lnf=0x3f3f3f3f3f3f3f3f;
    const double dnf=1e18;
    const int mod=1e9+7;
    const double eps=1e-8;
    const double pi=acos(-1.0);
    const int hp=13331;
    const int maxn=1000100;
    const int maxm=100100;
    const int maxp=100100;
    const int up=100100;
    
    char a[maxn],b[maxn];
    int nt[maxn];
    ll ans[maxn];
    
    void get(int n,int m)
    {
    memset(ans,0,sizeof(ans));
    nt[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j>0&&a[i]!=a[j+1]) j=nt[j];
        if(a[i]==a[j+1]) j++;
        nt[i]=j;
    }
    
    for(int i=1,j=0;i<=m;i++)
    {
        while(j>0&&(j==n||b[i]!=a[j+1])) j=nt[j];
        if(b[i]==a[j+1]) j++;
        ans[j]++;
    }
    for(int i=n;i>=1;i--)
        ans[nt[i]]+=ans[i];
    }
    
    int main(void)
    {
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",b+1,a+1);
        int n=strlen(a+1);
        int m=strlen(b+1);
        reverse(a+1,a+n+1);
        reverse(b+1,b+m+1);
        get(n,m);
        ll sum=0;
        for(int i=1;i<=n;i++)
            sum=(sum+ans[i]*i)%mod;
        printf("%lld\n",sum);
    }
    return 0;
    }