hdu6153 A Secret 扩展kmp

题目链接：https://vjudge.net/problem/HDU-6153

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

用了扩展KMP的板子，因为扩展KMP求出的extend[i]extend[i]表示的是ss的ii到strlen(s)−1strlen(s)−1字符和tt的最长公共前缀。题目中要求后缀，就将两个字符串reverse一下。这样的话，extend[i]extend[i]就变成了ss的前strlen(s)−istrlen(s)−i个字符和tt的最大公共后缀的长度。如果发现最大后缀长度为22的话，那么后缀长度为11的情况一定也出现了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+5;
int nex[maxn];
int extend[maxn];
char q[maxn];
char w[maxn];
const ll mod=1000000007;
///用int会wa
void get_next(char str[])
{
int i=0;
int p;
int len=strlen(str);
while(str[i]==str[i+1]&&i+1<len)
{
i++;
}
nex[1]=i;
p=1;
for(int i=2;i<len;i++)
{
if(nex[i-p]+i<nex[p]+p)
{
nex[i]=nex[i-p];
}
else
{
int
j=nex[p]+p-i;
if(j<0) j=0;
while(i+j<len&&str[j]==str[i+j])
{
j++;
}
nex[i]=j;
p=i;
}
}
}
void extendkmp(char s1[],char s2[])
{
int i=0;
int p;
int len1=strlen(s1);
int len2=strlen(s2);
get_next(s2);
while(s1[i]==s2[i]&&i<len2&&i<len1)
{
i++;
}
extend[0]=i;
p=0;
for(i=1;i<len1;i++)
{
if(nex[i-p]+i<extend[p]+p)
{
extend[i]=nex[i-p];
}
else
{
int
j=extend[p]+p-i;
if(j<0) j=0;
while(i+j<len1&&j<len2&&s1[j+i]==s2[j])
{
j++;
}
extend[i]=j;
p=i;
}
}
}
///extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(nex,0,sizeof(nex));
memset(extend,0,sizeof(extend));
scanf("%s",q);
scanf("%s",w);
int len1=strlen(q);
int len2=strlen(w);
reverse(q,q+len1);
reverse(w,w+len2);
get_next(w);
extendkmp(q,w);
ll ans=0;
for(int i=0;i<len1;i++)
{
if(extend[i])
{
//
for(int i=1;i<=extend[i];i++)
///会超时
//
{
//
ans++;
//
}
ans+=(extend[i]%mod)*((extend[i]+1)%mod)/2;
///等差数列的运用（求1~n的前n项和）。
ans%=mod;
}
}
printf("%lldn",ans);
}
}

最后

以上就是负责西装为你收集整理的hdu6153 A Secret 扩展kmp的全部内容，希望文章能够帮你解决hdu6153 A Secret 扩展kmp所遇到的程序开发问题。

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