Codeforces 444(#254 Div1) D. DZY Loves Strings

問題

文字列sが与えられる。次のようなクエリq個に答えよ。

sの連続する部分文字列で、文字列x, yをともに連続する部分文字列として含むような文字列のうち、長さが最小のものの長さを出力せよ。
そのような文字列が存在しない場合-1を出力せよ。

x, yはオーバーラップしていてもよい。

制約条件

s	≦50000
x	,	y	≦4

方針

出現頻度が√|s|回以上である文字列は少ない。
なので、√|s|回以上出現する文字列に対するクエリは予め全通り計算しておくことができる。
（|s|√|s|通り位置を計算すればよい）

出現頻度が√|s|回未満であるような文字列に対するクエリは普通に尺取法で計算すればいい。

ソースコード

bool contains(const string &a, const string &b){
	if(a.size() < b.size()) return 0;
	rep(i, a.size() - b.size() + 1) if(a.substr(i, b.size()) == b) return 1;
	return 0;
}

const int SZ = 400;
int n, q;
char s[50010];

int main(){
	scanf("%s%d", s, &q);
	n = strlen(s);
	
	unordered_map<ll, int> id;
	unordered_map<ll, vi> pos;
	unordered_map<ll, int> left[400], right[400];
	
	rep(i, n){
		ll h = 0;
		
		rep(j, 4) if(i + j < n){
			h = h * 29 + s[i + j] - 'a' + 1;
			pos[h].pb(i);
		}
	}
	
	int cur_id = 0;
	
	each(it, pos){
		if(it->second.size() < SZ) continue;
		id[it->first] = cur_id;
		
		const vi &v = it->second;
		int idx = 0;
		
		rep(i, n){
			ll h = 0;
			while(idx < v.size() && v[idx] < i) idx++;
			if(idx >= v.size()) break;
			
			rep(j, 4) if(i + j < n){
				h = h * 29 + s[i + j] - 'a' + 1;
				int d = v[idx] - i;
				
				if(!left[cur_id].count(h)) left[cur_id][h] = d;
				else left[cur_id][h] = min(left[cur_id][h], d);
			}
		}
		
		idx = v.size() - 1;
		for(int i = n - 1; i >= 0; i--){
			ll h = 0;
			while(idx >= 0 && v[idx] > i) idx--;
			if(idx < 0) break;
			
			rep(j, 4) if(i + j < n){
				h = h * 29 + s[i + j] - 'a' + 1;
				int d = i - v[idx];
				
				if(!right[cur_id].count(h)) right[cur_id][h] = d;
				else right[cur_id][h] = min(right[cur_id][h], d);
			}
		}
		cur_id++;
	}
	
	while(q--){
		char A[8], B[8], *a = A, *b = B;
		scanf("%s%s", A, B);
		int la = strlen(A), lb = strlen(B);
		ll ha = 0, hb = 0;
		rep(i, la) ha = ha * 29 + a[i] - 'a' + 1;
		rep(i, lb) hb = hb * 29 + b[i] - 'a' + 1;
		
		
		if(!pos.count(ha) || !pos.count(hb)){
			puts("-1");
			continue;
		}
		
		if(contains(a, b) || contains(b, a)){
			printf("%d\n", max(la, lb));
			continue;
		}
		
		int ca = pos[ha].size(), cb = pos[hb].size();
		if(ca < cb){
			swap(ca, cb); swap(ha, hb); swap(a, b); swap(la, lb);
		}
		
		if(ca >= SZ){
			int ix = id[ha];
			int ans = inf;
			if(left[ix].count(hb)) ans = min(ans, left[ix][hb] + la);
			if(right[ix].count(hb)) ans = min(ans, right[ix][hb] + lb);
			printf("%d\n", ans);
			continue;
		}
		
		const vi &va = pos[ha];
		const vi &vb = pos[hb];
		int ans = inf;
		
		for(int ia = 0, ib = 0; ia < ca; ia++){
			while(ib < cb && vb[ib] < va[ia]) ib++;
			if(ib >= cb) break;
			ans = min(ans, vb[ib] - va[ia] + lb);
		}
		for(int ia = 0, ib = 0; ib < cb; ib++){
			while(ia < ca && va[ia] < vb[ib]) ia++;
			if(ia >= ca) break;
			ans = min(ans, va[ia] - vb[ib] + la);
		}
		printf("%d\n", ans);
	}
	return 0;
}