HDU 6153 A Secret（扩展KMP算法）

原题

A Secret

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 256000/256000 K (Java/Others)

Problem Description

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.

Source

2017中国大学生程序设计竞赛 - 网络选拔赛

题意

在母串中找模式串的所有后缀的匹配次数，并乘上各种后缀对应长度，再把所有的结果加起来输出。

涉及知识及算法

吐槽：开始以为是KMP，做了很久都做不对。最后发现KMP会跳过一些情况，用扩展KMP是可以做的，但用KMP也不是不行，大神代码传送门： 点击打开链接

扩展KMP算法 传送门： 点击打开链接

把两个字符串都反转一下就变成了前缀匹配，就可以利用扩展KMP的性质了。因为extend[i] 表示的是从i到结尾的主串与模式串的最长公共前缀，这样遍历一遍主串，每一位对答案的贡献就是1+⋯+extend[i]=extend[i]×(extend[i]+1)/2，累加即可。

代码

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int MAXL=1e6+5;
char str1[MAXL],str2[MAXL];
int extend[MAXL],Next[MAXL];
int str1l,str2l;
//模式串自己和自己匹配
void GetNext()
{
    //a为已匹配位置之首，p为已匹配位置之尾
    int a=0,p=0;
    //从下标为0开始的匹配就是自己的长度
    Next[0]=str2l;
    //从下标为1开始匹配
    for(int i=1;i<str2l;i++)
    {
        //i>=p作用：举个例子，母串无一字符与模式串相同
        //i大于p或可以继续往后匹配
        if(i>=p||i+Next[i-a]>=p)
        {
            if(i>=p)
            {
                //更新尾位置
                p=i;
            }
            //往后匹配并更新尾位置
            while(p<str2l&&str2[p]==str2[p-i])
            {
                p++;
            }
            Next[i]=p-i;
            //更新首位置
            a=i;
        }
        else
        {
            Next[i]=Next[i-a];
        }
    }
}
//母串和模式串匹配,与求Next过程类似
void GetExtend()
{
    int a=0,p=0;
    GetNext();
    for(int i=0;i<str1l;i++)
    {
        if(i>=p||i+Next[i-a]>=p)
        {
            if(i>=p)
            {
                p=i;
            }
            while(p<str1l&&p-i<str2l&&str1[p]==str2[p-i])
            {
                p++;
            }
            extend[i]=p-i;
            a=i;
        }
        else
        {
            extend[i]=Next[i-a];
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    getchar();
    while(n--)
    {
        gets(str1);
        str1l=strlen(str1);
        reverse(str1,str1+str1l);
        gets(str2);
        str2l=strlen(str2);
        reverse(str2,str2+str2l);
        GetExtend();
        long long sum=0;
        for(int i=0;i<str1l;i++)
        {
            sum=(sum+((long long)extend[i]*(extend[i]+1)/2)%MOD)%MOD;
        }
        printf("%lld\n",sum);
    }
    return 0;
}