hdu 6153

给两个串s1,s2求s2所有的后缀的长度乘其在s1中出现的次数之和。
按照题意去枚举s2的后缀铁定是行不通的，对于一个后缀i，当s1中有一个后缀j的前缀i和其相等时，才会加1，而且与此同时，后缀i+1,i+1,…n-1的次数都会加1
考虑用exkmp解决
可知匹配串t和模式串s,next[i]表示s[i,len-1]与s[0,len-1]的最长公共前缀，extend[i]表示t[i,len2]与s[0,len-1]的最长公共前缀，如果用前缀去解决后缀相关的问题?
当然是把串都倒过来了。
将s1,s2倒置后s2的后缀就成了前缀，将s2当成是模式串，则extend[i]为k表示s[i-k+1,i]与s2[0,k]是完全相同的，而s1,s2是倒过来的，所以s2的长度为1,2…,k的后缀的次数都要加1，即i的贡献就是(extend[i] +1 ) * extend[i] /2

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
LL t,n,len1,len2,next[1010101],extend[1010101],ans;
char s1[1010101],s2[1010101];
const LL mod = 1e9+7;
void EKMP(int len1,int len2){
int j =0;
next[0] = len2;
while(j+1<len2&&s2[j]==s2[j+1]) j++;
next[1] = j;
int k = 1;
for(int i = 2;i<len2;i++){
int p = next[k] + k -1;
int L = next[i-k];
if(i+L<p+1) next[i] = L;
else {
j = std::max(0,p-i+1);
while(i+j<len2&&s2[i+j]==s2[j])j++;
next[i] =j;
k = i;
}
}
j = 0;k = 0;
while(j<len1&&j<len2&&s1[j]==s2[j]) j++;
extend[0] = j;
for(int i = 1;i<len1;i++){
int p = extend[k]+k-1;
int L = next[i-k];
if(i+L<p+1) extend[i] = L;
else{
j = std::max(0,p-i+1);
while(j<len2&&i+j<len1&&s1[i+j]==s2[j])j++;
extend[i] = j;
k =i;
}
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%s%s",s1,s2);
ans = 0;
len1 = strlen(s1);
len2 = strlen(s2);
std::reverse(s1,s1+len1);
std::reverse(s2,s2+len2);
EKMP(len1,len2);
for(int i = 0;i<len1;i++){
//printf("%d ",extend[i]) ;
ans += (1+extend[i])*extend[i]/2;
ans %=mod;
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是落寞悟空为你收集整理的hdu 6153的全部内容，希望文章能够帮你解决hdu 6153所遇到的程序开发问题。

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