本文主要是介绍A Secret HDU - 6153 扩展KMP || KMP，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：https://vjudge.net/problem/HDU-6153
题意
求一个串T的所有后缀在串S中出现的次数 ，最后再求和。

扩展KMP解法

可以利用拓展KMP求出S的每一个后缀和T的最长公共前缀。
假如当前最长公共前缀为k，就说明长度为k的前缀在S中出现了一次，并且这个k前缀不能构成k+1前缀。用一个cnt数组将各种长度前缀出现的次数记录下来。

对于样例2

abababab
aba

首先将样例翻转，得到

babababa
aba

拓展KMP求出的extend数组值如下

extend[0] = 0
extend[1] = 3
extend[2] = 0
extend[3] = 3
extend[4] = 0
extend[5] = 3
extend[6] = 0
extend[7] = 1

所以cnt数组值为

cnt[1] = 1
cnt[2] = 0
cnt[3] = 3

根据cnt数组来求T的前缀在S中出现的次数:

• 长度为3的前缀：出现了3次不解释。

• 长度为2的前缀：在长度为3的前缀中出现过3次，不能构成3前缀的2前缀数目(即cnt[2])等于0，所以2前缀出现了3次。

• 长度为1的前缀：在长度为2的前缀中出现了3次，不能构成2前缀的1前缀数目(即cnt[1])等于1，所以1前缀出现了4次。

问题解决

代码

KMP解法

KMP：和拓展KMP相似。
主要思路就是求出不能构成k + 1前缀的k前缀数目。
和 用KMP统计T串在S串中出现次数 的代码相似，KMP匹配的时候，我们只需要在失配和匹配完成的时候记录一下即可。
设失配的时候已经匹配的长度为k，那么这个k前缀不能构成k + 1前缀。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
const int N=1e6+5;
int n,m,nextval[N];
char s[N],t[N];
ll id[N];
const int mod=1e9+7;
void getNextval()
{
    int i=0,j=-1;
    nextval[0]=-1;
    while(i<m)
    {
        if(j==-1||t[i]==t[j])
            nextval[++i]=++j;
        else j=nextval[j];
    }
}
void KMP()
{
    getNextval();
    int i=0,j=0;
    while(i<n)
    {
        if(j==-1||s[i]==t[j]) ++i,++j;
        else j=nextval[j];
        id[j]++;
        if(j==m)
            j=nextval[j];
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(id,0,sizeof(id));
        scanf("%s%s",s,t);
        n=strlen(s),m=strlen(t);
        for(int i=0; i<=(n-1)/2; ++i)
            swap(s[i],s[n-1-i]);
        for(int i=0; i<=(m-1)/2; ++i)
            swap(t[i],t[m-1-i]);
        KMP();
        ll ans=0;
        for(int i=m; i>0; --i)
        {
            id[nextval[i]]+=id[i];
            ans=(ans+id[i]*i)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

原文：
https://blog.csdn.net/ECNU_LZJ/article/details/77477204

这篇关于A Secret HDU - 6153 扩展KMP || KMP的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！