[PKU/POJ][3294][Life Forms][后缀数组]

给你 n 个字符串，求出最长的子串，使得子串在大于一半的字符串中都出现。

先将 n 个字符串用 n 个不同的字符连接起来。求出 height 数组后，二分子串长度 k, 查找是否存在连续的大于 n/ 2+ 1 个后缀的 height 值都大于 k。这里要求这 n/ 2+ 1 都属于不同串，可以用一数组进行标记，具体做法详见代码。

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>

int const N= 200100;
int wa[N], wb[N], wv[N], ws[N];
int rank[N], height[N], sa[N], r[N], n, m;
int num[N], idx= 0, ins= 128;
int cnt[1010];
char str[1010];

int cmp( int* r, int a, int b, int L ){
	return r[a]== r[b] && r[a+ L]== r[b+ L];
}

void da( int* r, int* sa, int n, int m ){
	int i, j, p, *x= wa, *y= wb, *t;
	for( i= 0; i< m; ++i ) ws[i]= 0;
	for( i= 0; i< n; ++i ) ws[ x[i]= r[i] ]++;
	for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];
	for( i= n- 1; i>= 0; i-- ) sa[ --ws[ x[i] ] ]= i;
	
	for( j= 1, p= 1; p< n; j*= 2, m= p ){
		for( p= 0, i= n- j; i< n; ++i ) y[p++]= i;
		for( i= 0; i< n; ++i )
		if( sa[i]>= j ) y[p++]= sa[i]- j;
		
		for( i= 0; i< n; ++i ) wv[i]= x[ y[i] ];
		for( i= 0; i< m; ++i ) ws[i]= 0;
		for( i= 0; i< n; ++i ) ws[ wv[i] ]++;
		for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];
		for( i= n- 1; i>= 0; i-- ) sa[ --ws[ wv[i] ] ]= y[i];
		
		t= x, x= y, y= t; p= 1; x[ sa[0] ]= 0;
		for( i= 1; i< n; ++i )
		x[ sa[i] ]= cmp( y, sa[i-1], sa[i], j )? p- 1: p++;
	}
}

void calheight( int* r, int* sa, int n ){
	int i, j, k= 0;
	for( i= 1; i<= n; ++i ) rank[ sa[i] ]= i;
	
	for( i= 0; i< n; height[ rank[i++] ]= k )
	for( k? k--: 0, j= sa[ rank[i]- 1]; r[i+ k]== r[j+ k]; k++ );
}

int check( int mid ){
	for( int i= 0; i<= 1000; ++i ) cnt[i]= 0;
	int flag= 1, ans= 0;
	
	for( int i= 1; i<= n; ++i ){
		if( height[i]< mid ){
			cnt[ num[ sa[i] ] ]= ++flag; ans= 1;
		}
		else{
			if( cnt[ num[ sa[i] ] ]!= flag ) ans++;
			cnt[ num[ sa[i] ] ]= flag;
		}
		if( ans>= ( m/ 2+ 1) ) return 1;
	}
	return 0;
}

void print( int mid ){
	for( int i= 0; i<= 1000; ++i ) cnt[i]= 0;
	int ans= 0, flag= 1, isp= 0, beg;
	
	for( int i= 1; i<= n; ++i ){
		if( height[i]< mid ){
			cnt[ num[ sa[i] ] ]= ++flag; ans= 1; isp= 0; beg= sa[i];
		}
		else{
			if( cnt[ num[ sa[i] ] ]!= flag ) ans++;
			cnt[ num[ sa[i] ] ]= flag;
		}
		
		if( isp== 0 && ans>= (m/ 2+ 1 ) ){
			isp= 1;
			
			for( int j= 0; j< mid; ++j )
			printf("%c", r[ beg+ j] );
			
			puts("");
		}
	}
}

int main(){
	while( scanf("%d",&m)!= EOF ){
		getchar();
		if( m== 0 ) return 0;
		
		n= 0; ins= 128; idx= 0;
		for( int i= 0; i< m; ++i ){
			gets(str);
			int len= strlen(str); ++idx;
			for( int i= 0; i< len; ++i ) {
				num[n+ i]= idx; r[n+ i]= str[i]; }
			
			r[len+ n]= ins++;  len++; n+= len;
		}
		n--; r[n]= 0;
		
		da( r, sa, n+ 1, 500 );
		calheight( r, sa, n );		
		
		int left= 1, right= n;
		while( left<= right ){
			int mid= (left+ right)>>1;
			
			if( check( mid ) ) left= mid+ 1;
			else right= mid- 1;
		}
		
		if( right== 0 ) puts("?");
		else print( right );
		
		puts("");
	}
	
	return 0;
}