KUPC2014 K - 弱点

問題

日本語なので本文参照（http://kupc2014.contest.atcoder.jp/tasks/kupc2014_k）

文字列s1, s2, ... snの中のうち、文字列tを連続する部分文字列として含むものの個数をkとする。k * |t|の最大値を求めよ。

制約条件

n≦10^5
Σ|si|≦10^5

方針

とりあえず嘘解法で通した。
（オーダー的には嘘じゃないと思うんだけど、定数倍で嘘になっている）

自分の解法は以下の通り。
まず、全文字列を'$'のような適当な区切り記号で結合して一つの文字列にする。
で、そのsuffix arrayを構築する。

すると、tをk個のsiが含むというのは、
suffix arrayのx番目からy番目までにk個のユニークなsi由来の文字があって、
かつsuffix arrayのx番目からy番目までのLCPがkであるということになる。

ここで、kが多いとそうでない場合に分けて考えてみる。
kが多いとき、k個の文字列がtを含まないといけないためk*|t|≦10^5である。
したがって、文字列の長さが短くなる。
文字列の長さが短ければ、文字の長さlに対して、
各xについて、LCPがlになるようなyを、尺取法を用いればO(|S|)で求めることができる。

k≧Qのとき、この方針で解くとすると、計算量はO(|S|^2/Q)

kが少ないときは、それぞれのkに対して、
各xについて、ユニークなsiの個数がちょうどkになるようなyを尺取法を用いてO(|S|)で求めることができる。
k≦Qのときこの方針で解くとすると計算量はO(|S|Q)

したがって、Q = sqrt(|S|)とすれば、全体の計算量はO(|S|^3/2)になる。

ただし定数がでかいのと、後者の計算の定数が重めなので、Qを上手く調整してあげて、
なおかつ枝刈りを入れないと通らない。

やった枝刈りは自明なもので、
前回に見た長さで一番よかったやつを使っても解が更新されないならスキップ、
前回に見たユニークな個数で一番よかったときのを使っても解が更新されないならスキップ。

ソースコード

//buildSAはO(nlogn)
//minimumはほぼO(1)
//buildLCPはO(n)

const int MX = 100010;
int n, len[MX], pos[MX], which[MAX_LEN];
char in[MAX_LEN];


int main(){
	memset(which, -1, sizeof(which));
	
	scanf("%d", &n);
	rep(i, n){
		scanf("%s", in + pos[i]);
		pos[i + 1] = pos[i] + (len[i] = strlen(in + pos[i])) + 1;
		
		rep(j, len[i]) which[pos[i] + j] = i;
	}
	rep(i, n - 1) in[pos[i + 1] - 1] = '$';
	
	
	buildSA(in);
	buildLCP(in);
	
	int N = pos[n];
	int *rmq = buildRMQ(lcp, N + 1);
	int ans = *max_element(len, len + n);
	int lensum = accumulate(len, len + n, 0);
	
	//rep(i, N) cerr<<lcp[i] << " " << in + si[i] << endl;
	
	const int THRESHOLD = 200;
	
	//出現が少ない解
	int best = inf;
	for(int tm = 2; tm <= THRESHOLD; tm++){
		
		if(tm > n) break;
		if((ll)best * tm <= ans) continue;
		int type = 0;
		static int cnt[MX];
		memset(cnt, 0, sizeof(cnt));
		
		best = 0;
		
		for(int i = 1, j = 1; i <= N; i++){
			
			while(j <= N && type < tm){
				if(which[si[j]] >= 0 && cnt[which[si[j]]]++ == 0) type++;
				j++;
			}
			
			if(type < tm) break;
			if(i + 1 <= j - 1){
				int l = minimum(i + 1, j - 1, rmq, N + 1);
				best = max(best, l);
				ans = max(ans, type * l);
			}
			if(which[si[i]] >= 0 && --cnt[which[si[i]]] == 0) type--;
		}
	}
	
	//長さの短い解
	best = inf;
	for(int l = 1; l * THRESHOLD <= lensum; l++){
		
		if((ll)best * l <= ans) continue;;
		
		int type = 0;
		static int cnt[MX];
		memset(cnt, 0, sizeof(cnt));
		
		best = 0;
		
		for(int i = 1, j = 1; i < N - 1; i++){
			
			while(j <= i + 1){
				if(which[si[j]] >= 0 && cnt[which[si[j]]]++ == 0) type++;
				j++;
			}
			
			int cur_len = minimum(i + 1, j - 1, rmq, N + 1);
			if(cur_len >= l){
				while(j <= N && cur_len >= l){
					if(which[si[j]] >= 0 && cnt[which[si[j]]]++ == 0) type++;
					
					cur_len = min(cur_len, lcp[j++]);
				}
				
				if(cur_len >= l) break;
				j--;
				if(which[si[j]] >= 0 && --cnt[which[si[j]]] == 0) type--;
				
				if(i + 1 <= j - 1){
					ans = max(ans, type * l);
				}
			}
			best = max(best, type);
			if(which[si[i]] >= 0 && --cnt[which[si[i]]] == 0) type--;
		}
	}
	
	cout << ans << endl;
	
	return 0;
}