题意:给一串单词依次连接(第一个和第二个,加起来再和第三个......),连接时前一个单词和后一个单词最长的前后缀重合,问最后的句子
拿来复习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; }