hdu6153 扩展kmp求一个字符串的后缀在另一个字符串出现的次数。

/**

题目：hdu6153

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6153

题意：给定两个串，求其中一个串t的每个后缀在另一个串s中出现的次数乘以其长度之和。

思路：扩展kmp

先将两个字符串翻转过来。那么变成求t串每个前缀在s串出现的次数。

直接扩展kmp求出extend[i]表示s串[i,n-1]子串和t串的最长公共前缀。

那么s串从i开始和t串前缀有匹配的贡献为1+2+...+extend[i] = extend[i]*(extend[i]+1)/2；

*/

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

#include <iostream>

#include <cmath>

#include <vector>

#include <map>

using namespace std;

typedef long long LL;

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int, int> P;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + ;

const int maxn = 1e6+;

char s[maxn], t[maxn];

int Next[maxn], extend[maxn];

int cnt[maxn];

LL ans;

void GetNext(char *T,int* next)

{

    int a=;

    int Tlen=strlen(T);

    next[]=Tlen;

    while(a<Tlen-&&T[a]==T[a+]) a++;

    next[]=a;

    a=;

    for(int k=;k<Tlen;k++)

    {

        int p=a+next[a]-,L=next[k-a];

        if((k-)+L>=p)

        {

            int j=(p-k+)>? p-k+:;

            while(k+j<Tlen&&T[k+j]==T[j]) j++;

            next[k]=j;

            a=k;

        }

        else next[k]=L;

    }

}

void GetExtend(char *S,char *T,int* next,int* extend)

{

    int a=;

    GetNext(T,next);

    int Slen=strlen(S);

    int Tlen=strlen(T);

    int MinLen=Slen<Tlen? Slen:Tlen;

    while(a<MinLen&&S[a]==T[a]) a++;

    extend[]=a;

    a=;

    for(int k=;k<Slen;k++)

    {

        int p=a+extend[a]-,L=next[k-a];

        if((k-)+L>=p)

        {

            int j=(p-k+)>? p-k+:;

            while(k+j<Slen&&j<Tlen&&S[k+j]==T[j]) j++;

            extend[k]=j;

            a=k;

        }

        else extend[k]=L;

    }

}

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        scanf("%s%s",s,t);

        ms(cnt,);

        int n = strlen(s);

        int m = strlen(t);

        reverse(s,s+n);

        reverse(t,t+m);

        GetExtend(s,t,Next,extend);

        ans = ;

        for(int i = ; i < n; i++){

            ans = (ans+(LL)extend[i]*(extend[i]+)/)%mod;

        }

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

    }

    return ;

}