pku 3294-接尾辞ツリーグループ-3

 http://poj.org/problem?id=3294
題意:100文字列を与えて、すべての列の総文字数は100000を超えないで、最も長い1つの列を求めてこの列が>n/2の列の中で現れたことを保証します.複数ある場合は、辞書順に出力します.の
 
解析:接尾辞配列+二分の問題をずっと書いたことがある.いつもコントロールが悪い.の
他のテーマと同様に、これらのシリアルを異なる文字で区切って1つのシリアルにすることが考えられます.のheight配列を求め,次いで二分最長の列の長さを求め,この最大長を求める.長さごとに判断する場合は、height配列をスキャンし、連続する>=temp_lenの区間の接尾辞はn/2より大きい原列から来ているかどうか..最後に出力する場合は判断時と同様の方法でOKです..
 
同類テーマ:
pku 3080は最も長い列を求めてすべての列の中で現れます...pku 1226は、すべての(本列またはその逆置きの列)に1つの列が現れることを求める.の
注意:このような問題を解決する時n=1は必ず単独で考えなければならない..の入力したパラメータは必ず文字の数より大きくなければなりません.そうしないとRE...
 
 
コード:

#include<stdio.h>
#include<string.h>

#define maxn 101001
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
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];
       for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
       x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
     }
     return;
}
int rank[maxn],height[maxn];
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++);
     return;
}

int len1, len, n, up, mx;
char s[maxn], s1[maxn];
int sa[maxn], a[maxn], cate[maxn];
int flag[110];

int check(int tlen)
{
	int i, j, k, cnt;
	i = j = 1;
	while(i<=len && j<=len)
	{
		for(k=0; k<n; k++)
			flag[k] = 0;
		while(height[i]<tlen && i<=len)
			i++;
		j=i;
		while(height[j]>=tlen && j<=len)
			j++;
		if(j-i+2<=n/2)
		{
			i=j;
			continue;
		}
		for(k=i-1; k<j; k++)
		{
			if(cate[sa[k]]!=-1)//     ，wa        。。。
				flag[cate[sa[k]]] = 1;
		}
		for(cnt=0,k=0; k<n; k++)
			cnt += flag[k];
		if(cnt>n/2)
			return 1;
		i = j;
	}
	return 0;
}
void print(int tlen)
{
	if(tlen==0)
	{
		printf("?
");
		return;
	}
	int i, j, k, cnt;
	i = j = 1;
	while(i<=len && j<=len)
	{
		for(k=0; k<n; k++)
			flag[k] = 0;
		while(height[i]<tlen && i<=len)
			i++;
		j=i;
		while(height[j]>=tlen && j<=len)
			j++;
		if(j-i+2<=n/2)
		{
			i=j;
			continue;
		}
		for(k=i-1; k<j; k++)
		{
			if(cate[sa[k]]!=-1)
				flag[cate[sa[k]]] = 1;
		}
		for(cnt=0,k=0; k<n; k++)
			cnt += flag[k];
		if(cnt>n/2)
		{
			for(k=0; k<tlen; k++)
				printf("%c", a[sa[i]+k]-1);
			printf("
");
		}
		i = j;
	}
}

void solve()
{
	int l, r, ans, mid;
	l=0, r=mx;
	while(l<=r)
	{
		mid = (l+r)>>1;
		if(check(mid))
			l = mid + 1;
		else
			r = mid - 1;
	}
	ans = r;
	//printf("%d.....
", ans);//...
	print(ans);
}
int main()
{
	int i, j, k;
	scanf("%d", &n);
	while(1)
	{
		if(n==0)
			break;
		up = 140;
		mx = 1;
		for(i=0, j=0; i<n; i++)
		{
			scanf("%s", s1);
			len1 = strlen(s1);
			if(len1>mx)
				mx = len1;
			for(k=0; k<len1; k++)
			{
				cate[j] = i;
				a[j++] = s1[k]+1; // 1           。。
			}
			cate[j] = -1;
			a[j++] = up+i;
		}
		a[--j] = 0;
		len = j;
		
		if(n==1)
		{
			printf("%s
", s1);
			continue;
		}
		da(a, sa, len+1, 250);
		calheight(a, sa, len);
		//for(i=0; i<=len; i++)//..................
		//	printf("i=%2d..%2d %2d..
", i, sa[i], height[i]);
		solve();
		
		scanf("%d", &n);
		if(n==0)
			break;
		else
			printf("
");
	}
	return 0;
}