E. Compress Words
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Amugae has a sentence consisting of $$$n$$$ words. He want to compress this sentence into one word. Amugae doesn't like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges "sample" and "please" into "samplease".
Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.
Input
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of the words in Amugae's sentence.
The second line contains $$$n$$$ words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits ('A', 'B', ..., 'Z', 'a', 'b', ..., 'z', '0', '1', ..., '9'). The total length of the words does not exceed $$$10^6$$$.
Output
In the only line output the compressed word after the merging process ends as described in the problem.
Examples
input
Copy
output
Copy
input
Copy
5
sample please ease in out
output
Copy
题意：
题意:给N个由大小写字母、数字组成的字符串，两个字符串S,T合并时，删除T最长的是S的后缀的前缀，然后接在一起。现将这些字符串依次合并，求最终字符串。
分析：
双Hash
保存一个最终答案字符串str1，当前正在比较的字符串str2，比如说
fedefabc abc
我们需要求出两个字符的最大的Hash匹配值，abc=int(a)*p^2+int(b)*p^1+int(c)*p^0
但我们可以一遍循环就可以搞定，具体看代码，如果你了解Hash的话，应该很容易。
这题的坑点就是可能会卡单Hash，双Hash的话，注意，要构造好，Hash一般很迷。
ULL，虽然时间，但很容易被卡。提供两种解决法案，
- UUL+mod1：1000000000+7
- mod1：1000000000+7+mod2：1000000000+9
第一种快一点。
KMP
求是裸着求str2能在str1匹配的最远即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int mod1=1000000000+7;
const int mod2=1000000000+9;
typedef unsigned int UI;
const int N=5000005;
const int P=131;
const int P1=131;
char str1[N],str2[N];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",str1+1);
int len1=strlen(str1+1);
for(int i=1; i<n; i++)
{
scanf("%s",str2+1);
int len2=strlen(str2+1);
ULL hash1=0,hash2=0;
LL hash3=0,hash4=0;
ULL pw=1;
LL pw1=1;
int ed=min(len1,len2),res=0;
for(int j=1; j<=ed; j++)
{
hash1=(hash1+pw*int(str1[len1-j+1]));
hash2=(hash2*P+int(str2[j]));
pw=((P)*(pw));
hash3=(hash3*P1+int(str1[len1-j+1]))%mod2;
hash4=(hash4+int(str2[j])*pw1)%mod2;
pw1=((P1%mod2)*(pw1%mod2))%mod2;
//cout<<str1[len1-j+1]<<" "<<str2[j]<<endl;
//cout<<hash1<<" "<<hash2<<endl;
if(hash1==hash2&&hash3==hash4)
{
res=j;
}
}
//cout<<res<<endl;
for(int j=res+1;j<=len2;j++)
{
len1++;
str1[len1]=str2[j];
}
}
printf("%s",str1+1);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int mod1=1000000000+7;
const int mod2=1000000000+9;
typedef unsigned int UI;
const int N=5000005;
const int P=131;
const int P1=131;
char str1[N],str2[N];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",str1+1);
int len1=strlen(str1+1);
for(int i=1; i<n; i++)
{
scanf("%s",str2+1);
int len2=strlen(str2+1);
LL hash1=0,hash2=0;
LL hash3=0,hash4=0;
LL pw=1;
LL pw1=1;
int ed=min(len1,len2),res=0;
for(int j=1; j<=ed; j++)
{
hash1=(hash1+pw*int(str1[len1-j+1]))%mod1;
hash2=(hash2*P+int(str2[j]))%mod1;
pw=((P%mod1)*(pw%mod1))%mod1;
hash3=(hash3*P1+int(str1[len1-j+1]))%mod2;
hash4=(hash4+int(str2[j])*pw1)%mod2;
pw1=((P1%mod2)*(pw1%mod2))%mod2;
//cout<<str1[len1-j+1]<<" "<<str2[j]<<endl;
//cout<<hash1<<" "<<hash2<<endl;
if(hash1==hash2&&hash3==hash4)
{
res=j;
}
}
//cout<<res<<endl;
for(int j=res+1;j<=len2;j++)
{
len1++;
str1[len1]=str2[j];
}
}
printf("%s",str1+1);
return 0;
}
KMP
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
const int N = 10000002;
int nxt[N];
char S[N], T[N],str1[N],str2[N];
int slen, tlen;
void getNext()
{
int j, k;
j = 0;
k = -1;
nxt[0] = -1;
while(j < tlen)
if(k == -1 || T[j] == T[k])
{
nxt[++j] = ++k;
if (T[j] != T[k]) //优化
nxt[j] = k;
}
else
k = nxt[k];
}
/*
返回模式串T在主串S中首次出现的位置
返回的位置是从0开始的。
*/
int KMP_Index()
{
int i = max(slen-tlen,0), j = 0;
getNext();
while(i < slen && j < tlen)
{
if(j == -1 || S[i] == T[j])
{
i++;
j++;
}
else
j = nxt[j];
}
return j;//T串前缀在主串S可以匹配的最远可以匹配的位置
if(j == tlen)
return i - tlen;
else
return -1;
}
int main()
{
int n;
scanf("%d",&n);
scanf("%s",S);
slen=strlen(S);
for(int i=1; i<n; i++)
{
scanf("%s",T);
tlen = strlen(T);
int pos=KMP_Index();
//cout<<pos<<endl;
for(int j=pos;j<tlen;j++)
{
S[slen]=T[j];
slen++;
}
}
printf("%s",S);
return 0;
}
