AtCoder ARC #055 : C - ABCAC

こっちの方がBよりすんなり解けたな。
http://arc055.contest.atcoder.jp/tasks/arc055_c

問題

N文字の文字列Sが与えられる。
この文字列を、３つの空でない文字列A,B,Cを用いてS=ABCACと表現できるようなA,B,Cの組み合わせは何通りあるか。

解法

部分点解法として、ローリングハッシュを用いた総当たりがある。
A,Cの長さを決めるとABCACの各文字列の位置が決まるので、２つのA及びCに相当する位置に対するSの部分文字列が一致するかハッシュで確認すればよい。
これはO(N^2)かかるので|S|が大きいケースはTLEする。

Aが先頭、Cが末尾にあることを利用すると、中にあるCAの部分が先頭のA,末尾のCと一致するかをZ-algorithmで高速に求められる。
最初にS及びSを反転した文字列に対しZ-algorithmを適用しておこう。

ABC=S[0..(x-1)], AC=S[x..(L-1)]とSを前後２つに分割しよう(Bが空でないので、前者の方が長くなくてはならない)
後者のAC=S[x..(L-1)]に対し、Aとしてあり得る文字列の最大長L(A)はZ-algorithmよりS[x..(L-1)]とSのprefixの最大一致長となる。
またCとしてあり得る候補の文字列長L(C)は反転文字列に対するZ-algorithmよりS[0..(x-1)]とSのsuffixの最大一致長となる。
ただA,Cは1文字以上取らないといけないのでL(A),L(C)の最大値は(L-x-1)に抑える。

こうすると、L(A)+L(C)≧L-xなら条件を満たすA,Cが存在し、その組み合わせはL(A)+L(C)-(L-x)+1通り。
各分割位置xに対し上記値の総和を取るとそれが解。

今回はZ-algorithmを用いたので計算量はO(N)だが、L(A),L(C)を求めるパートはローリングハッシュの二分探索によるO(N*logN)解法でも間に合うようだ。

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;
}

vector<int> Z1,Z2;

string S;
int L;
void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>S;
	L=S.size();
	Z1=Zalgo(S);
	reverse(ALL(S));
	Z2=Zalgo(S);
	reverse(ALL(S));
	reverse(ALL(Z2));
	
	ll ret=0;
	for(x=2;x<L;x++) if(x>L-x) {
		int pre=min(L-x-1,Z1[x]);
		int post=min(L-x-1,Z2[x-1]);
		if(pre<1 || post<1) continue;
		int len=pre+post;
		if(len>=L-x) ret += min(len-(L-x)+1,(L-x-1));
	}
	
	cout<<ret<<endl;
	
}

まとめ

思いつけて良かったね。