kmjp's blog

競技プログラミング参加記です

Codeforces #578 Div2 E. Compress Words

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よりだいぶ簡単だね。