UVa 1227 The longest constant gene

問題

A,C,G,Tからなる文字列n個が与えられる。
n個全てに出現する文字列のうち、最も長さの長い文字列の長さを求めよ。

制約条件

n≦6
それぞれの文字列の長さは100万以下

方針

S1 + "$1" + S2 + "$2" + ... + "$n"という文字列の
suffix arrayを作る。

（ただし$iは適当な区切り文字）
suffix arrayからLCPを求めて、
LCPの配列を尺取する。

suffix arrayの値から、そのsuffixが何番目の文字列由来かがわかる。
全ての文字列由来の文字が含まれている区間について、
その区間上のLCPの最小値の最大値が求める答えになる。
これは蟻本にあった本の問題のような尺取をしつつ、
最小値はdeqを使って増加するところだけを覚えておくようにすればO(len)で出来る。

TLEが厳しく、suffix arrayの構築にO(len log len)をかけるとTLE.

O(n)のsuffix arrayの構築はhttp://www.cs.sysu.edu.cn/nong/index.files/Two%20Efficient%20Algorithms%20for%20Linear%20Suffix%20Array%20Construction.pdfにコードが載ってた。

ソースコード

const int MX = 6000100;
char in[MX];
int n, m, len[MX], deq[MX];
int which[MX], sa[MX], lcp[MX], b[MX];
void buildLCP(char *t, int n, int *a, int *lcp) {
	int h = 0;
	rep(i, n+1) b[a[i]] = i;
	rep(i, n+1) {
		if (b[i]){
			for (int j = a[b[i]-1]; j+h<n && i+h<n && t[j+h] == t[i+h]; ++h);
			lcp[b[i]] = h;
		} else lcp[b[i]] = -1;
		if (h > 0) --h;
	}
}

int main(){
	int cs; scanf("%d", &cs);
	while(cs--){
		scanf("%d", &n);
		m = 0;
		rep(i,n){
			scanf("%s", in+m);
			len[i] = strlen(in+m);
			m += len[i];
			in[m++] = '0' + i;
			len[i] = m;
		}
		len[m] = 0;
		SA_IS((unsigned char*)in, sa, m+1, 256, sizeof(char));
		buildLCP(in, m, sa, lcp);
		
		int cur = 0;
		rep(i,m+1){
			if(i == len[cur] - 1) which[b[i]] = n, cur++;
			else which[b[i]] = cur;
		}
		
		int ans = 0, k = 0, use[6] = {}, h = 0, t = 0;
		for(int l = 0, r = 0; l < m; l++){
			while(l > r) r++;
			while(r <= m && k < n){
				int idx = which[r];
				if(idx < n && use[idx]++ == 0) k++;
				while(h < t && lcp[deq[t-1]] >= lcp[r]) t--;
				if(r) deq[t++] = r;
				r++;
			}
			if(k < n) break;
			ans = max(ans, lcp[deq[h]]);
			
			if(h < t && deq[h] <= l+1) h++;
			int idx = which[l];
			if(idx < n && --use[idx] == 0) k--;
		}
		printf("%d\n", ans);
	}
	return 0;
}