hdu-6153 A Secret

题意：给两个字符串，求第二个字符串的所有后缀在第一个字符出现次数的   次数*长度的总和。

思路：将两个串反转，则变成了求第二个串的所有前缀在第一个字符出现的次数。此时：我们可以用KMP匹配两个串，失配时的位置的之前位置必然是已经匹配好的。那么：我们只要在失配的位置 i 或者整个串匹配完的位置 给累加答案，代表 0 - i位置都匹配好一次。然后最后再去处理答案。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define LL long long
#define siz 1000005
using namespace std;
const int mod = 1e9+7;
char str[2*siz],s[siz];
int nex[siz];
int ans[siz];
void kmp_pre(char x[],int m){
int i,j;
j = nex[0] = -1;
i = 0;
while(i < m){
if(j==-1 || x[i] == x[j])
nex[++i] = ++j;
else j = nex[j];
}
}
void KMP_Count(char x[],int m,char y[],int n){
int i,j;
kmp_pre(x,m);
i = j = 0;
/* for(int i=0;i<m;i++){
cout<<nex[i]<<endl;
}*/
for(i = 0; i < n; i++)
{
while(j && y[i] != x[j])
{
// cout<<i<<"---"<<j<<endl;
ans[j]++;
j = nex[j];
}
if(y[i] == x[j])
{
j++;
}
if(j == m)
{
//cout<<i<<"&&&"<<j<<endl;
ans[j]++;
j = nex[j];
}
}
// cout<<i<<"^^^"<<j<<endl;
//if(j<m) ans[j] += 1;
}
void solve(){
int len1 = strlen(str);
int len2 = strlen(s);
/*for(int i=0;i<len1/2;i++){
swap(str[i],str[len1-i-1]);
}*/
strrev(str);
strrev(s);
for(int i=0;i<len2;i++){
str[i+len1] = '-';
}
str[len2+len1] = '';
len1 = len2 + len1;
/*for(int i=0;i<len2/2;i++){
swap(s[i],s[len2-i-1]);
}*/
///puts(str);
//puts(s);
KMP_Count(s,len2,str,len1);
LL res = 0;
LL r = 0;
for(int i=len2;i>=0;i--){
//cout<<i<<" "<<ans[i]<<endl;
r =(r + ans[i])%mod;
res = (res + (((1ll*i)%mod)*(r%mod)%mod)) % mod;
}
printf("%lldn",res);
}
int main()
{
int T;
scanf("%dn",&T);
while(T--){
memset(ans,0,sizeof(ans));
scanf("%s",str);
scanf("%s",s);
solve();
}
return 0;
}

最后

以上就是害怕大象为你收集整理的hdu-6153 A Secret的全部内容，希望文章能够帮你解决hdu-6153 A Secret所遇到的程序开发问题。

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