AtCoder ABC #135 : F - Strings of Eternity

ABCとしては最長のコードになってしまった。
https://atcoder.jp/contests/abc135/tasks/abc135_f

問題

文字列S,Tが与えられる。
Sを無限に連結したとき、その部分列として、Tを最大何個連結したものが現れるか。

解法

Editorialの方がすっきりしてるけど、一応自分の解法を紹介。
文字列判定はローリングハッシュ(RH)を使ってるけど、Prefixとの一致しか判定してないのでZ-Algorithmで行ける。

まず、解が無限大になるケースを考える。
これはS,Tがともに(回転させると同じ文字列になる)文字列の繰り返しで構成されている場合である。
よって、両者の最短周期を求め(これは|S|と|T|の約数を周期の候補として総当たりし、RHで周期性をチェックすればよい)、周期が一致している場合は片方を順に回転させて文字列一致を判定すればよい。

そうでない場合、Tを連結したもののはS中で現れたとしても|S|未満の長さの物となる。
よってSの各位置から見て、Tを何個連結したものと一致するか、やはりRHで一致判定しながら見ていこう。
各位置から最大|S|/|T|弱の個数だけ連結したものと一致する可能性があるので、各位置に対し毎回愚直に調べるとTLEする。

二分探索にするとか、|T|だけずれた位置における結果を再利用とかしたほうがよい。
下記のコードは後者である。

struct RollingHash {
	static const ll mo0=1000000021,mo1=1000000009;
	static ll mul0,mul1;
	static const ll add0=1000010007, add1=1003333331;
	static vector<ll> pmo[2];
	string s; int l; vector<ll> hash_[2];
	void init(string s) {
		this->s=s; l=s.size(); int i,j;
		hash_[0]=hash_[1]=vector<ll>(1,0);
		if(!mul0) mul0=10009+(((ll)&mul0)>>5)%259,mul1=10007+(((ll)&mul1)>>5)%257;
		if(pmo[0].empty()) pmo[0].push_back(1),pmo[1].push_back(1);
		FOR(i,l) hash_[0].push_back((hash_[0].back()*mul0+add0+s[i])%mo0);
		FOR(i,l) hash_[1].push_back((hash_[1].back()*mul1+add1+s[i])%mo1);
	}
	pair<ll,ll> hash(int l,int r) { // s[l..r]
		if(l>r) return make_pair(0,0);
		while(pmo[0].size()<r+2)
			pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1);
		return make_pair((hash_[0][r+1]+(mo0-hash_[0][l]*pmo[0][r+1-l]%mo0))%mo0,
			             (hash_[1][r+1]+(mo1-hash_[1][l]*pmo[1][r+1-l]%mo1))%mo1);
	}
	pair<ll,ll> hash(string s) { init(s); return hash(0,s.size()-1); }
	static pair<ll,ll> concat(pair<ll,ll> L,pair<ll,ll> R,int RL) { // hash(L+R) RL=len-of-R
		while(pmo[0].size()<RL+2) pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1);
		return make_pair((R.first + L.first*pmo[0][RL])%mo0,(R.second + L.second*pmo[1][RL])%mo1);
	}
};
vector<ll> RollingHash::pmo[2]; ll RollingHash::mul0,RollingHash::mul1;

RollingHash RS,RT;
string S,T;
int A,B;
int num[2020202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	A=S.size();
	B=T.size();
	S+=S+S;
	T+=T;
	RS.init(S);
	RT.init(T);
	
	int PS,PT;
	for(x=1;x<=A;x++) if(A%x==0) {
		for(i=x;i<A;i+=x) if(RS.hash(0,x-1)!=RS.hash(i,i+x-1)) break;
		if(i==A) {
			PS=x;
			break;
		}
	}
	for(x=1;x<=B;x++) if(B%x==0) {
		for(i=x;i<B;i+=x) if(RT.hash(0,x-1)!=RT.hash(i,i+x-1)) break;
		if(i==B) {
			PT=x;
			break;
		}
	}
	
	if(PS==PT) {
		FOR(y,PS) {
			if(RT.hash(0,PT-1)==RS.hash(y,y+PS-1)) {
				cout<<-1<<endl;
				return;
			}
		}
		cout<<0<<endl;
		return;
	}
	
	int ma=0;
	FOR(x,A) {
		if(x>=B && num[x-B]) {
			num[x]=num[x-B]-1;
		}
		else {
			FOR(i,A) {
				if(x+(i+1)*B>3*A) break;
				if(RT.hash(0,B-1)!=RS.hash(x+i*B,x+(i+1)*B-1)) break;
			}
			num[x]=i;
		}
		ma=max(ma,num[x]);
	}
	cout<<ma<<endl;
	
}

まとめ

Eとセットで割と時間がかかった。