题意:
将给定的单词去掉最长的相同前后缀拼接起来。
思路:
双hash
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod1=1e9+7;
const int mod2=1e9+9;
const int p=131;
const int N=5e6+5;
char s1[N],s2[N];
int main(){
int n;
scanf("%d",&n);
scanf("%s",s1+1);
int l1=strlen(s1+1);
for(int i=1;i<n;i++){
scanf("%s",s2+1);
int l2=strlen(s2+1);
ll hash1=0,hash2=0,hash3=0,hash4=0,pw1=1,pw=1;
int res=0,sz=min(l1,l2);
for(int j=1;j<=sz;j++){
hash1=(hash1+pw*(int)(s1[l1-j+1]))%mod1;
hash2=(hash2*p+(int)(s2[j]))%mod1;
pw=(pw%mod1)*p%mod1;
hash3=(hash3+pw1*(int)(s1[l1-j+1]))%mod2;
hash4=(hash4*p+(int)(s2[j]))%mod2;
pw1=(pw1%mod2)*p%mod2;
if(hash1==hash2&&hash3==hash4)
res=j;
}
for(int j=res+1;j<=l2;j++)
l1++,s1[l1]=s2[j];
}
printf("%s\n",s1+1);
return 0;
}