Codeforces 90D (119D) String Transformation

問題

長さnの文字列sと整数i, jに対して、次の関数を定義する。
f(s, i, j) = s[i+1...j-1] + r(s[j...n]) + r(s[0...i])

ただし、+は文字列の結合を、r(s)は文字列の反転を表すものとする。
二つの文字列a, bが与えられる。
f(a, i, j) = bを満たすi, jのうち、iを最大にし、同じiに対してはjを最小にするi, jを求めよ。
存在しない場合は-1 -1を出力せよ。

制約条件

文字列の長さ≦10^6

方針

二つの文字列の長さは同じとしてよい。

iは全通りループをまわす。
a[i+1...n-1]と、b[0...n-i-1]の部分を一致させるようなjを、
短い時間で見つけられればよい。

これは実はO(1)でできて、
r(a)$bという文字列のKMPのfailure linkをp[i]とする。
このとき、j = n - p[2 * n - i - 1]である。

これはjの候補のうち、最も小さいものであるが、
ここでa[i+1...j-1]とb[0...j-i-2]が一致しなかった場合、
これ以上大きいjでも絶対一致しないので、この候補だけvalidであるか調べればよい。

このjがvalidであるかは、
b$aという文字列のz配列を見ればよくて、
（z[i]は、s.substr(i)とsが何文字一致するかを表す配列で、O(n)で前計算できる）
z[n+2+i]が、j-i-1以上になっていればよい。

ソースコード

int *buildZ(const string &s){
	int n = s.size();
	int *z = new int[n];
	int l = 0, r = 0;
	
	memset(z, 0, sizeof(int)*n);
	for(int i = 1; i < n; i++){
		if(i <= r) z[i] = min(z[i - l], r - i + 1);
		while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
		if(i + z[i] - 1 > r){
			l = i;
			r = i + z[i] - 1;
		}
	}
	return z;
}
int* buildFail(const string &s){
	int n = s.size();
	int *p = new int[n];
	p[0] = 0;
	for (int i = 1; i < n; ++i){
		p[i] = p[i - 1];
		while (p[i] > 0 && s[p[i]] != s[i]) p[i] = p[p[i] - 1];
		if (s[p[i]] == s[i]) p[i]++;
	}
	return p;
}

string r(string s){
	reverse(all(s));
	return s;
}

int main(){
	string a, b;
	getline(cin, a);
	getline(cin, b);
	
	if(a.size() != b.size()){
		cout << "-1 -1" << endl;
		return 0;
	}
	
	int n = a.size();
	string s = r(a) + '\0' + b;
	string t = b + '\0' + a;

	int *fail = buildFail(s);
	int *z = buildZ(t);
	
	int ai = -1, aj = -1;
	rep(i, n - 1){
		if(a[i] != b[n - i - 1]) break;
		int len = fail[2 * n - i - 1];
		if(z[n + i + 2] >= n - i - len - 1){
			ai = i;
			aj = n - len;
		}
	}
	cout << ai << " " << aj << endl;
	
	return 0;
}