HDU 6153 A Secret（扩展KMP+数学推导）

ゞ浴缸里的玫瑰 2022-06-09 05:07 171阅读 0赞

Today is the birthday of SF,so VS gives two strings S1,S2 to SF as a present,which have a big secret.SF is interested in this secret and ask VS how to get it.There are the things that VS tell:  
Suffix(S2,i) = S2\[i...len\].Ni is the times that Suffix(S2,i) occurs in S1 and Li is the length of Suffix(S2,i).Then the secret is the sum of the product of Ni and Li.  
Now SF wants you to help him find the secret.The answer may be very large, so the answer should mod 1000000007.

Input

Input contains multiple cases.  
The first line contains an integer T,the number of cases.Then following T cases.  
Each test case contains two lines.The first line contains a string S1.The second line contains a string S2.  
1<=T<=10.1<=|S1|,|S2|<=1e6.S1 and S2 only consist of lowercase ,uppercase letter.

Output

For each test case,output a single line containing a integer,the answer of test case.  
The answer may be very large, so the answer should mod 1e9+7.

Sample Input

2
    aaaaa
    aa
    abababab
    aba

Sample Output

13
    19

Hint

case 2: 
    Suffix(S2,1) = "aba",
    Suffix(S2,2) = "ba",
    Suffix(S2,3) = "a".
    N1 = 3,
    N2 = 3,
    N3 = 4.
    L1 = 3,
    L2 = 2,
    L3 = 1.
    ans = （3*3+3*2+4*1）%1000000007.

题解：

在CCPC网赛的时候没想出来。。。比完以后自己用KMP试了好多次都超时，后来看别人的题解原来是扩展KMP。。。然后我又去刷了几天的扩展KMP。。还是做不出来这题。。。没办法又看别人的题解（弱渣哭晕在电脑前），发现真的太巧妙了，原来不仅仅要用拓展KMP，还要一些数学推导

题意：

给你一个主串，一个匹配串，每次匹配串删去前面最前面的一个字符再进行匹配，然后结果是当前匹配串长度x在主串中出现的次数，求所有的累加和

思路：

我一开始想的是将两个字符串反转。。每次在匹配串的最后一个变为‘\\0’，然后用KMP求在主串中的出现次数，然后累加。。。。然后数据范围是1e6，毫无疑问华丽得超时了。。。。别人的做法很巧妙，他就是求了一遍匹配串在主串中的最长公共前缀和用extend保存，然后可以发现对于主串的每一位对答案的贡献是1+2+...ex\[i\]，也就是ex\[i\]\*(ex\[i\]+1)/2，这个好好想一想就可以想明白。。最后遍历一遍ex数组累加答案就行了，还有要注意一点%mod的时候要除完2再模，要不然答案是错的。。我就是因为这个WA了几遍，用上的是求最长公共前缀的扩展KMP的模板

ps:

将字符串反转是因为题目要求每次去掉匹配串的第一个，不太好操作，两个字符串一起反转匹配的结果是相同的，就相当于每次从最后面去掉了一个字符来计算

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 100861111
    #define ll long long
    #define eps 1e-15
    const ll N=1e9+7;
    int Next[1000005];
    int ex[1000005];
    void EKMP(char s[],char t[],int Next[],int extend[])//s为主串，t为模板串
    {
        int i,j,p,L;
        int lens=strlen(s);
        int lent=strlen(t);
        Next[0]=lent;
        j=0;
        while(j+1<lent && t[j]==t[j+1])j++;
        Next[1]=j;
        int a=1;
        for(i=2;i<lent;i++)
        {
            p=Next[a]+a-1;
            L=Next[i-a];
            if(i+L<p+1)Next[i]=L;
            else
            {
                j=max(0,p-i+1);
                while(i+j<lent&&t[i+j]==t[j])j++;
                Next[i]=j;
                a=i;
            }
        }
        j=0;
        while(j<lens&&j<lent&&s[j]==t[j])j++;
        extend[0]=j;
        a=0;
        for(i=1;i<lens;i++)
        {
            p=extend[a]+a-1;
            L=Next[i-a];
            if(L+i<p+1)extend[i]=L;
            else
            {
                j=max(0,p-i+1);
                while(i+j<lens&&j<lent&&s[i+j]==t[j])j++;
                extend[i]=j;
                a=i;
            }
        }
    }
    int main()
    {
        int i,j,len1,len2,t;
        char s1[1000005],s2[1000005];
        scanf("%d",&t);
        while(t--)
        {
            scanf("%s%s",s1,s2);
            len1=strlen(s1);
            len2=strlen(s2);
            reverse(s1,s1+len1);
            reverse(s2,s2+len2);
            EKMP(s1,s2,Next,ex);
            ll ans=0;
            for(i=0;i<len1;i++)
            {
                ans=(ans+(((ll)ex[i]*(ex[i]+1))/2)%N)%N;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }