Zepto Code Rush 2015 : D. Om Nom and Necklace

Z Algorithm使うのCodeforcesばかりだなぁ…。
http://codeforces.com/contest/526/problem/D

問題

N文字の文字列Sと整数Kが与えられる。

Sにおける各i文字のprefix S[0..(i-1)]において、２つの文字列A,Bを用いてS[0..(i-1)]=A+B+A+B+...+A (Aを(K+1)回とBをK回)と表現可能かどうかを求めよ。

解法

最後のAを除くと、S[0..(i-1)]=C*K+Aと表現できるかを判定する問題となる。

Z algorithmを用いて、Cとしてc=1～N/K文字のSのprefixを総当たりし、S[0..(c*K-1)]=S[0..(c-1)]*Kかどうかを判定する。

S[0..(c*K-1)]=S[0..(c-1)]*Kである場合、S[0..(c*K+i)]=S[0..(c-1)]*K+S[0..i]を満たすかどうかを判定すればよい。
上記条件を満たす場合、A=S[0..i]、B=[(i+1)..(c-1)]とするとS[0..(c*K+i)]が条件を満たすことになる。

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);
		}
	}
	return v;
}

int L,K;
string S,T;
int LL[1001000],SS[2001000];
vector<int> Z;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>K>>S;
	
	Z=Zalgo(S);
	
	for(x=1;x*K<=L;x++) {
		FOR(y,K) if(Z[y*x]<x) break;
		if(y==K) LL[x*K-1]=x;
	}
	ll t=0;
	FOR(i,L) if(LL[i]) {
		SS[i]++;
		SS[min(i+LL[i]+1,i+1+Z[i+1])]--;
	}
	
	x=0;
	FOR(i,L) x+=SS[i], T+=x?'1':'0';
	cout<<T<<endl;
}

まとめ

本番はRollingHashで解いてしまった。