Div. 2 E. Compress Words（KMP）
题意：给一串单词依次连接（第一个和第二个，加起来再和第三个......），连接时前一个单词和后一个单词最长的前后缀重合，问最后的句子
拿来复习KMP。。实在太久没写过KMP了,
KMP通过求解最长相同前后缀进行字符串匹配，next数组为最长长度表右移一位得到。
KMP过程中求得是：模式串的前缀与母串的后缀最长相同长度
i代表当前母串匹配位置，每轮匹配 j 初始值为i-1位置母串对应的最长相同前后缀末端位置+1，
如果此时满足，母串[ i ]=模式串[ j+1 ]，则当前最长相同前后缀末端为nxt[ i-1 ]+1 (++j)
因为nxt数组其实是长度表右移，所以最后求 next数组代码为：
//对tmp求nxt
int len=tmp.length();
int j=0;
nxt[0]=nxt[1]=0;
for(int i=2;i<=len;++i)
{
while(j&&tmp[i-1]!=tmp[j]) j=nxt[j];
if(tmp[i-1]==tmp[j]) ++j;
nxt[i]=j;
} 题中要求tmp与答案串中，tmp的前缀与答案串的后缀的最长相同长度，套板子 #include<bits/stdc++.h>
using namespace std;
#define endll '\n'
#define C getchar()
typedef long long ll;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 998244353
#define pii pair<int, int>
const int MAXN = 1e6 + 10;
#define stop system("pause")
#define lowbit(x) ((x) & (-x))
#define Temp template<typename T>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define fast std::ios::sync_with_stdio(false)
Temp inline void rd(T &s)
{
s = 0;T t = 1, k = C;
for (; k < '0' || k > '9'; k = C)if (k == '-') t = -1;
for (; k >= '0' && k <= '9'; k = C) s = (s << 1) + (s << 3) + (k ^ 48);
s *= t;
}
string a;
int nxt[MAXN];
int main()
{
int n;rd(n);
cin>>a;
for(int _=1;_<n;++_)
{
string tmp;
cin>>tmp;
//对tmp求nxt
int len=tmp.length();
int j=0;
nxt[0]=nxt[1]=0;
for(int i=2;i<=len;++i)
{
while(j&&tmp[i-1]!=tmp[j]) j=nxt[j];
if(tmp[i-1]==tmp[j]) ++j;
nxt[i]=j;
}
j=0;
int anslen=a.length();
for(int i=max(1,anslen-len+1);i<=anslen;++i)
{
while(j&&a[i-1]!=tmp[j]) j=nxt[j];
if(a[i-1]==tmp[j]) ++j;
}
for(int i=j;i<len;++i) a+=tmp[i];
}
cout<<a<<endll;
//stop;
return 0;
} 
地平线工作强度 166人发布
