6問とはいえ妙に簡単だった回。
https://codeforces.com/contest/1200/problem/E
問題
N個の単語があるので、それを順に連結した単語を構築せよ。
2つの単語A,Bを連結するとは以下の作業を意味する。
AのSuffixとBのPrefixが一致する最長の文字数iがあったとき、Aの後ろにBのprefix i文字を取り除いたものを付与する。
解法
1個ずつ単語を連結した文字列を順に作っていけばよい。
AのSuffixとBのprefixの最長一致を求めればよいので、Bと区切り文字の後ろにAのsuffixをmin(|A|,|B|)文字くっつけてZ-algorithmを行おう。
Aはどんどん長くなるが、毎回高々O(|B|)で1回の単語連結が終わるので、全体でO(総文字列長)の時間で終わる。
int N; string S[101010]; string T; vector<int> Zalgo(string s) { vector<int> v(1,s.size()); for(int i=1,l=-1,r=-1;i<s.size();i++) { if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]); else { l=i; r=(i>r)?i:(r+1); while(r<s.size() && s[r-i]==s[r]) r++; v.push_back((r--)-l); } } v.push_back(0); return v; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>S[i]; string G=S[i]+"$"+T.substr(T.size()-min(T.size(),S[i].size())); auto Z=Zalgo(G); int ma=0; for(x=S[i].size()+1;x<G.size();x++) if(x+Z[x]==G.size()) ma=max(ma,Z[x]); T+=S[i].substr(ma); } cout<<T<<endl; }
まとめ
普段のDiv2Eよりだいぶ簡単だね。