HDU - 6153 A Secret （KMP）

题面：

题意：
给定两个串 $b, a$ ，对于 $a$ 中的每一个后缀 $a [i, l e n]$ ，求其在 $b$ 串中出现了多少次。
输出 $\sum_{i = 1}^{l e n} l e n (a [i, l e n]) * c n t$ ，其中 $c n t$ 为 $a [i, l e n]$ 在 $b$ 串中出现的次数。

题解：
我们将两个串都翻转一下，转化为前缀，然后做kmp，最后在逆向更新一遍 $a n s$ 数组。

代码：

#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;
}