Codeforces #246 Div2 D. Prefixes and Suffixes

そんなアルゴリズム知らない…。
http://codeforces.com/contest/432/problem/D

問題

長さNの文字列Sがある。
Sのprefixのうち、suffixと一致するものがあれば、そのprefixがS中substringとして登場する回数を答えよ。

解法

prefixとsuffixの一致判定は置いておいて、先にprefixの登場回数を全て列挙してしまう。
後はそのうちprefixとsuffixが一致するものだけ出力すればよい。

prefixの登場回数を高速にカウントするため、Z algorithmが適用できる。
自分はこれを知らなかったので参考リンクを張っておく。
Z algorithm - コードの恵み
Z Algorithm - Codeforces

このアルゴリズムを用いると、文字列中の各位置を開始位置とする部分文字列が、元の文字列のprefixと最大何文字一致するかをO(N)で求められる。

あとは、各prefixにおいて、上記最大文字一致数がprefixの長さ以上のものを数え上げればよい。
これは事前に累積和を取ればO(N)である。

vector<int> Zalgo(string s) {
	int l=-1,r=-1,i;
	vector<int> v;
	v.push_back(s.size());
	for(i=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);
		}
	}
	return v;
}

string S;
int num[100001],sum[100001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	
	int N=S.size();
	vector<int> V = Zalgo(S);
	vector<pair<int,int> > R;
	FOR(i,N) num[V[i]]++;
	for(i=N;i>=0;i--) sum[i]=sum[i+1]+num[i];
	for(i=1;i<=N;i++) if(V[N-i]==i) R.push_back(make_pair(i,sum[i]));
	_P("%d\n",R.size());
	FOR(i,R.size()) _P("%d %d\n",R[i].first,R[i].second);
}

まとめ

これを機会にZ algorithmをライブラリ化しておいた。
SuffixArrayでも解けるらしいので勉強しとこうかな…。