HDU 6153(A Secret)

题意：给定一个母串 S 和子串 h，求 h 的所有后缀在母串中的出现次数，设当前后缀长度为 Li，出现次数为 Ni，累加所有的 Li*Ni,并对1000000007取模。

分析：扩展KMP，变形一下，把母串 S 和子串 h 都反转过来，这样 h 的所有后缀即变成了 reverse(h) 的所有前缀，把 reverse(S) 当作母串，reverse(h) 当作模式串进行扩展KMP，extend[i]即表示 reverse(S) 以 i 为起始的后缀与 reverse(h) 的最长公共前缀，所以这个点对答案的贡献就是 （extend[i]+1）* extend[i] /2  .. 为什么，因为若最长公共前缀长度是extend[i]，那么长度为 extend[i]-1，extend[i]-2，...，1 的也是以这个点为起始的公共前缀，每个公共前缀出现一次对于答案的贡献即它的长度，所以这个点的所有公共前缀的长度和即为这个点对于答案的贡献。即 1+2+...+extend[i]

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define mod 1000000007
using namespace std;
const int N = 1E6+10;
char a[N],b[N],tmp[N];
int nxt[N];
int extend[N];
int n,m;
void GetNxt(char s[],int len,int nxt[])
{
int i=0,j,po;
nxt[0]=len;
while(s[i]==s[i+1]&&i+1<len) i++; nxt[1]=i;
po=1;
for(i=2;i<len;i++)
{
if(nxt[i-po]+i<nxt[po]+po) nxt[i]=nxt[i-po];
else
{
j=nxt[po]+po-i;
if(j<0) j=0;
while(i+j<len&&s[j]==s[j+i]) j++; nxt[i]=j;
po=i;
}
}
}
void ExKMP(char a[],int lena,char b[],int lenb)
{
int i=0,j,po;
while(a[i]==b[i]&&i<lena&&i<lenb) i++; extend[0]=i;
po=0;
for(i=1;i<lena;i++)
{
if(nxt[i-po]+i<extend[po]+po)
extend[i]=nxt[i-po];
else
{
j=extend[po]+po-i;
if(j<0) j=0;
while(i+j<lena&&j<lenb&&a[j+i]==b[j]) j++; extend[i]=j;
po=i;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",tmp);
n=strlen(tmp);
for(int i=0;i<n;i++) a[i]=tmp[n-i-1];
scanf("%s",tmp);
m=strlen(tmp);
for(int i=0;i<m;i++) b[i]=tmp[m-i-1];
GetNxt(b,m,nxt);
ExKMP(a,n,b,m);
long long ans=0;
for(int i=0;i<n;i++)
{
ans=(ans+(long long)extend[i]*(extend[i]+1)/2)%mod;
}
printf("%lldn",ans);
}
}

最后

以上就是轻松火为你收集整理的HDU 6153(A Secret)的全部内容，希望文章能够帮你解决HDU 6153(A Secret)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。