后缀数组十三题

本文移植自个人的原博客（原文）

论文

后缀数组——处理字符串的有力工具–罗穗骞

题目

POJ1743 Musical Theme

本题题目描述与论文略有差别。

应处理的字符串为所给数据的差值，且两个不可重叠最长重复子串不能紧挨着，此时虽不会产生重叠，但会共用同一个音符。（故判断条件应为 maxsa - minsa > k，而不是maxsa - minsa > = k（然而POJ并没有卡我..））

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5+1;
const int maxf = 255;
const int inf = 0x7fffffff;
int wa[N],wb[N],wv[N],tong[N],h[N],sa[N],rank[N],d[N];
int s[N];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int n,int m)
{
	int i,j,p,*x=wa,*y=wb;
	for(i=0;i<m;i++)tong[i]=0;
	for(i=0;i<n;++i)tong[x[i]=s[i]]++;
	for(i=1;i<m;++i)tong[i]+=tong[i-1];
	for(i=n-1;i>=0;--i)sa[--tong[x[i]]]=i;
	for(p=1,j=1;p<n;j<<=1,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++)tong[i]=0;
	    for(i=0;i<n;++i)tong[wv[i]]++;
	    for(i=1;i<m;++i)tong[i]+=tong[i-1];
	    for(i=n-1;i>=0;--i)sa[--tong[wv[i]]]=y[i];
	    for(swap(x,y),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;
}
void getheight(int n)
{
	int i,j,k=0;
	for(i=1;i<=n;++i)rank[sa[i]]=i;
	for(i=0;i<n;h[rank[i++]]=k)
	for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
	return;
}
bool can(int k,int n)
{
	int tmp=0,maxsa=-1,minsa=inf;
	for(int i=1;i<=n;++i)
	{
	    if(h[i]<k)maxsa=-1,minsa=inf;
	    if(sa[i]<minsa)minsa=sa[i];
	    if(sa[i]>maxsa)maxsa=sa[i];
	    if(maxsa-minsa>k)return 1;
	}
	return 0;
}
int main()
{
	//  freopen("theme.in","r",stdin);
	//  freopen("theme.out","w",stdout);
	int n,x;
	while(scanf("%d",&n)!=EOF)
	{
	    memset(h,0,sizeof(h));
	    memset(sa,0,sizeof(sa));
	    memset(rank,0,sizeof(rank));
	    if(!n)break;
	    cin>>x;
	    for(int i=1;i<n;++i)scanf("%d",&s[i]);
	    s[0]=s[1]-x;
	    for(int i=1;i<n-1;++i)s[i]=s[i+1]-s[i];
	    n--;
	    for(int i=0;i<n;++i)s[i]+=150;
	    da(n+1,maxf);
	    getheight(n);
	    int l=0,r=1e6,ans;
	    int mid=0;
	    while(l!=r)
	    {
	        ans=l+r+1>>1;
	        if(can(ans,n))  l=ans;
	        else      r=ans-1;
	    }
	    l++;
	    printf("%d\n",(l)>=5?l:0);
	}
}

POJ3261 Milk Patterns

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxf = 255;
const int inf = 0x7fffffff;
const int N = 1e5+5;
int sa[N],tong[N],wa[N],wb[N],wv[N],rank[N],height[N];
int s[N],k;
int cmp(int*r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int n,int m)
{
    int i,j,p,*x=wa,*y=wb;
    for(i=0;i<m;++i)tong[i]=0;
    for(i=0;i<n;++i)tong[x[i]=s[i]]++;
    for(i=1;i<m;++i)tong[i]+=tong[i-1];
    for(i=n-1;i>=0;--i)sa[--tong[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,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++)tong[i]=0;
        for(i=0;i<n;i++)tong[wv[i]]++;
        for(i=1;i<m;i++)tong[i]+=tong[i-1];
        for(i=n-1;i>=0;i--)sa[--tong[wv[i]]]=y[i];
        for(swap(x,y),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;
}
void getheight(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];s[i+k]==s[j+k];k++);
    return;
}
bool can(int ans,int n)
{
    int tot=0;
    for(int i=1;i<=n;++i)
    {
        if(height[i]<ans)tot=0;
        tot++;
        if(tot==k)return 1;
    }
    return 0;
}
int main()
{
    int n;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i)scanf("%d",s+i);
    da(n+1,maxf);
    getheight(n);
    int l=1,r=n+1,ans,mid;
    while(l!=r)
    {
        int mid=(l+r>>1)+1;
        if(can(mid,n))ans=l=mid;
        else    r=mid-1;
    }
    printf("%d\n",ans);
}

SPOJ694 Distinct Substrings

这题论文中的方法不太好想，可以换一种思路。

易证长度为$len$的字符串一共有$(len+1)∗len/2$个子串。

而其中重复的字串个数则为height数组的总和，减去即可。

以这一组数据为例，

sa[i-1]  abba
sa[i]    abcd //height[i] = 2

两者相同的字串有$2∗(2+1)/2=3$个。刚开始我不知道为什么这里要减去$2$而不是$3$，后来知道是因为只能减去包含该后缀首个字符的字串个数，否在会导致重复计算。

这个例子中只应减去$a,ab$这两个重复字符，之后必有两个后缀为

bba
bcd //height = 1

重复的子串$b$ 将在此处减掉。

#include<iostream> 
#include<cstring>
#include<cstdio>
const int N =1e4+5;       
using namespace std;       
char s[N];   
int sa[N],wa[N],wb[N],tong[N],wv[N];      
int rank[N],height[N];      
int cmp(int*r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int n,int m)
{
    int i,j,p,*x=wa,*y=wb;
    for(i=0;i<m;++i)tong[i]=0;
    for(i=0;i<n;++i)tong[x[i]=s[i]]++;
    for(i=1;i<m;++i)tong[i]+=tong[i-1];
    for(i=n-1;i>=0;--i)sa[--tong[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,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++)tong[i]=0;
        for(i=0;i<n;i++)tong[wv[i]]++;
        for(i=1;i<m;i++)tong[i]+=tong[i-1];
        for(i=n-1;i>=0;i--)sa[--tong[wv[i]]]=y[i];
        for(swap(x,y),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;
}
void calheight(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];s[i+k]==s[j+k];k++);
    return;
}
int main()  
{  
    int t;  
    scanf("%d",&t);  
    while(t--)  
    {  
        int i;  
        scanf("%s",s);  
        int n=strlen(s);   
        da(n+1,128);  
        calheight(n);  
        long long ans=n*(n+1)/2;  
        for(i=1;i<=n;i++)  
        ans-=height[i];  
        printf("%lld\n",ans);  
    }  
}

SPOJ705 不同的子串

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5+1;
const int maxf = 255;
int wa[N],wb[N],wv[N],tong[N],sa[N],rank[N],h[N];
char s[N];
bool cmp(int*r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int n,int m)
{
	int i,j,p,*x=wa,*y=wb;
	for(i=0;i<m;++i)tong[i]=0;
	for(i=0;i<n;++i)tong[x[i]=s[i]]++;
	for(i=1;i<m;++i)tong[i]+=tong[i-1];
	for(i=n-1;i>=0;i--)sa[--tong[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,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)tong[i]=0;
		for(i=0;i<n;++i)tong[wv[i]]++;
		for(i=1;i<m;++i)tong[i]+=tong[i-1];
		for(i=n-1;i>=0;--i)sa[--tong[wv[i]]]=y[i];
		for(swap(x,y),p=1,i=1,x[sa[0]]=0;i<n;++i)
		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
	return;
}
void getheight(int n)
{
	int i,j,k=0;
	for(i=1;i<=n;++i)rank[sa[i]]=i;
	for(i=0;i<n;h[rank[i++]]=k)
	for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
	return;
}
int main()
{
//  freopen("subst1.in","r",stdin);
//  freopen("subst1.out","w",stdout);
	scanf("%s",s);
	int n=strlen(s);
	da(n+1,maxf);
	getheight(n);
	for(int i=1;i<=n;++i)sa[i]++;
	long long ans=0;
	for(int i=1;i<=n;++i)ans+=n-sa[i]-(i==1?0:h[i])+1;
	printf("%d",ans);
}

URAL1297 Palindrome

这题坑很多，一开始没看论文自己写。先是常规操作，将字符串逆序加在原字符串后面，然后二分判断是否存在长度为height[i]>=mid的子串，且sa[i-1],sa[i]是否不属于同一部份子串，并在倒过来后能首尾相连，但由于没判奇偶被各种数据卡的死去活来。后来换了题解的思路AC了这题。

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e4+1;
int tong[N],wv[N],wa[N],wb[N];
int rank1[N],height[N],sa[N];
char s[N];
int a[N],n;
int dp[N][30];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int n,int m)
{
    int i,j,p,*x=wa,*y=wb;
    for(i=0;i<m;++i)tong[i]=0;
    for(i=0;i<n;++i)tong[x[i]=a[i]]++;
    for(i=1;i<m;++i)tong[i]+=tong[i-1];
    for(i=n-1;i>=0;--i)sa[--tong[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,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++)tong[i]=0;
        for(i=0;i<n;i++)tong[wv[i]]++;
        for(i=1;i<m;i++)tong[i]+=tong[i-1];
        for(i=n-1;i>=0;i--)sa[--tong[wv[i]]]=y[i];
        for(swap(x,y),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;
}

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

void preRMQ()
{
    int i,j;
    memset(dp,127,sizeof(dp));
    for(i=1;i<=n*2+1;i++)dp[i][0]=height[i];
    for(j=1;(1<<j)<=2*n+1;j++)
    for(i=1;i+(1<<j)-1<=2*n+1;i++)
    dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}

int lcp(int l,int r)
{
    int a=rank1[l],b=rank1[r];
    if(a>b)swap(a,b);
    a++;
    int t=(int)(log(double(b-a+1))/log(2.00));
    return min(dp[a][t],dp[b-(1<<t)+1][t]);
}

int main()
{
    int i,res,flag,max;
    while(scanf("%s",s)!=EOF)
    {
        max=0;
        n=strlen(s);
        for(i=0;i<n;i++)a[i]=(int)s[i];
        a[n]=1;
        for(i=0;i<n;i++)a[i+n+1]=int(s[n-i-1]);
        a[2*n+1]=0;
        da(2*n+2,123);
        calheight(2*n+1);
        preRMQ();
        for(i=0;i<n;i++)
        {
            res=lcp(i,2*n-i)*2-1;
            if(max<res)max=res,flag=i;
            if(i>0)
            {
                res=lcp(i,2*n-i+1)*2;
                if(max<res) max=res,flag=i;
            }
        }
        if(max%2==1)for(i=flag-max/2;i<=flag+max/2;i++)   printf("%c",s[i]);
        else for(i=flag-max/2;i<=flag+max/2-1;i++) printf("%c",s[i]);
        printf("\n");
    }
}

POJ2406 Power Strings

本题正解为DC3或KMP，倍增会TLE。论文中的时间复杂度均以DC3为依据，倍增要再乘个$logn$。

POJ3693 Maximum repetition substring

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5+1;
const int maxf = 255;
int sa[N],h[N],wa[N],wb[N],wv[N],tong[N],pre[N],rank[N];
int k,now,jj,maxr,cnt;
int d[N][21],ans[N];
char s[N*2];
bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}

void da(int n,int m)
{
	int i,j,p,*x=wa,*y=wb;
	for(i=0;i<m;++i)tong[i]=0;
	for(i=0;i<n;++i)tong[x[i]=s[i]]++;
	for(i=1;i<m;++i)tong[i]+=tong[i-1];
	for(i=n-1;i>=0;--i)sa[--tong[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,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<m;++i)tong[i]=0;
		for(i=0;i<n;++i)wv[i]=x[y[i]];
		for(i=0;i<n;++i)tong[wv[i]]++;
		for(i=1;i<m;++i)tong[i]+=tong[i-1];
		for(i=n-1;i>=0;--i)sa[--tong[wv[i]]]=y[i];
		for(swap(x,y),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++;
  }
}
void getheight(int n)
{
	int i,j,k=0;
	for(i=1;i<=n;++i)rank[sa[i]]=i;
	for(i=0;i<n;h[rank[i++]]=k)
	for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
}
int prermq(int*a,int n)
{
	for(int i=0;i<n;++i)d[i][0]=a[i];
	for(int j=1;(1<<j)<=n;++j)
	for(int i=0;i+(1<<j)-1<n;++i)
	d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int askrmq(int l,int r)
{
	l=rank[l],r=rank[r];
	if(l>r)swap(l,r);
	l++;
	int k=0;
	while((1<<(k+1))<=r-l+1)k++;
	return min(d[l][k],d[r-(1<<k)+1][k]);
}
int main()
{
	int ccase=0;
	while(1)
	{
		memset(h,0,sizeof(h));
		memset(d,0,sizeof(d));
		memset(tong,0,sizeof(tong));
		memset(rank,0,sizeof(rank));
		memset(ans,0,sizeof(ans));
		ccase++;
		k=now=jj=maxr=cnt=0;
		scanf("%s",s);
		if(s[0]=='#')return 0;
		int n=strlen(s);
		da(n+1,maxf);
		getheight(n);
		prermq(h,n+1);
		for(int i=1;i<n;++i) 
		for(int j=0;j+i<n;j+=i) 
		{
			k=askrmq(j,j+i);
			now=k/i+1;
			jj=j-(i-k%i);
			if (jj>=0&&askrmq(jj,jj+i)>=(i-k%i))++now;
			if(now>maxr)    {cnt=0;maxr=now;ans[cnt++]=i;}
			else if(now==maxr)  ans[cnt++]=i;
		}
		for(int i=1;i<=n;++i) 
		for(int j=0;j<cnt;++j)
		if(askrmq(sa[i],sa[i]+ans[j])>=(maxr-1)*ans[j])
		{
		    jj=sa[i],k=ans[j];
		    goto dd;
		}
		dd:;
		printf("Case %d: ",ccase);
		for (int i=0;i<maxr*k;++i)putchar(s[jj++]);
		printf("\n");
	}
}

SPOJ687 重复的字符串

暂略。

POJ2774 Long Long Message

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 3e5+1;
const int maxf = 255;
const int inf =0x7fffffff;
int sa[N],wa[N],wb[N],wv[N],tong[maxf+1],rank[N],h[N];
char s[N],ss[N];
bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int n,int m)
{
    int i,j,p,*x=wa,*y=wb;
    for(i=0;i<m;++i)tong[i]=0;
    for(i=0;i<n;++i)tong[x[i]=s[i]]++;
    for(i=1;i<m;++i)tong[i]+=tong[i-1];
    for(i=n-1;i>=0;--i)sa[--tong[x[i]]]=i;
    for(j=1,p=1;p<n;m=p,j<<=1)
    {
        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)tong[i]=0;
        for(i=0;i<n;++i)tong[wv[i]]++;
        for(i=1;i<m;++i)tong[i]+=tong[i-1];
        for(i=n-1;i>=0;--i)sa[--tong[wv[i]]]=y[i];
        for(swap(x,y),p=1,i=1,x[sa[0]]=0;i<n;++i)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
void geth(int n)
{
    int i,j,k=0;
    for(i=1;i<=n;++i)rank[sa[i]]=i;
    for(i=0;i<n;h[rank[i++]]=k)
    for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
}
int main()
{
    freopen("longlongmessage.in","r",stdin);
    freopen("longlongmessage.out","w",stdout);
    scanf("%s",s);
    scanf("%s",ss);
    int n=strlen(s),m=strlen(ss);
    s[n]='*';
    for(int i=n+1;i<=n+m;++i)s[i]=ss[i-n-1];
    int l=n+m+1;
    da(l+1,maxf);
    geth(l);
    int maxx=0;
    for(int i=2;i<=l;++i)
    {
        if(h[i]>maxx&&((sa[i]<n&&sa[i-1]>n)||(sa[i]>n&&sa[i-1]<n)))
        maxx=h[i];
    }
    cout<<maxx;
}

POJ3415 Common Substrings

暂略。

POJ3294 生命形态

本题和上题都是多个字符串的问题，将其拼在一起时，应在加上不同的分隔符号，否则会被不友善的数据卡掉。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e5+1;
const int inf =0x7fffffff;
const int maxf = 255;
bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
int sa[N],wa[N],wb[N],wv[N],rank[N],h[N],tong[N];
char ss[111][10001],s[N];
int nn[111],tt;
bool inq[111];
int ll[N];
void da(int n,int m)
{
    int i,j,p,*x=wa,*y=wb;
    for(i=0;i<m;++i)tong[i]=0;
    for(i=0;i<n;++i)tong[x[i]=s[i]]++;
    for(i=1;i<m;++i)tong[i]+=tong[i-1];
    for(i=n-1;i>=0;--i)sa[--tong[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,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<m;++i)tong[i]=0;
        for(i=0;i<n;++i)tong[wv[i]=x[y[i]]]++;
        for(i=1;i<m;++i)tong[i]+=tong[i-1];
        for(i=n-1;i>=0;--i)sa[--tong[wv[i]]]=y[i];
        for(i=1,p=1,swap(x,y),x[sa[0]]=0;i<n;++i)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
void geth(int n)
{
    int i,j,k=0;
    for(i=1;i<=n;++i)rank[sa[i]]=i;
    for(i=0;i<n;h[rank[i++]]=k)
    for(j=sa[rank[i]-1],k?k--:0;s[j+k]==s[i+k];k++);
}
int k;
int ansg;
bool can(int ans,int n,int flag)
{
    if(!flag)
    {
        int tot1=0;
        memset(inq,0,sizeof(inq));
        for(int i=1;i<=n;++i)
        {
            if(h[i]<ans)
            {
                memset(inq,0,sizeof(inq));  tot1=0;
            }
            else
            {
                int nowq,nowt;
                for(int t=1;t<=tt;++t)if(nn[t-1]<sa[i-1]&&sa[i-1]<nn[t])nowt=t;
                for(int t=1;t<=tt;++t)if(nn[t-1]<sa[i]&&sa[i]<nn[t])nowq=t;
                if(!inq[nowq])tot1++,inq[nowq]=true;
                if(!inq[nowt])tot1++,inq[nowt]=true;
                if(tot1>=k)return 1;
            }
        }
        return 0;
    }
    if(flag)
    {
      int lll=inf,rrr=-1;
      int tot1=0;
      memset(inq,0,sizeof(inq));
      for(int i=1;i<=n;++i)
      {
          if(h[i]<ans)
          {
              memset(inq,0,sizeof(inq));  tot1=0;
              lll=inf;rrr=-1;
          }
          else
          {
              int nowq,nowt;
              if(sa[i-1]<lll)lll=sa[i-1];if(sa[i-1]>rrr)rrr=sa[i-1];
              if(sa[i]<lll)lll=sa[i];if(sa[i]>rrr)rrr=sa[i];
              for(int t=1;t<=tt;++t)if(nn[t-1]<sa[i-1]&&sa[i-1]<nn[t])nowt=t;
              for(int t=1;t<=tt;++t)if(nn[t-1]<sa[i]&&sa[i]<nn[t])nowq=t;
              if(!inq[nowq])tot1++,inq[nowq]=true;
              if(!inq[nowt])tot1++,inq[nowt]=true;
              if(tot1==k)ll[++ansg]=lll;
          }
      }
  }
}
int main()
{
//  freopen("Lifeforms.in","r",stdin);
//  freopen("Lifeforms.out","w",stdout);
    while(scanf("%d",&tt)!=EOF)
    {
        if(!tt)return 0;
        memset(wa,0,sizeof(wa));
        memset(wb,0,sizeof(wb));
        memset(wv,0,sizeof(wv));
        memset(rank,0,sizeof(rank));
        memset(sa,0,sizeof(sa));
        memset(h,0,sizeof(h));
        memset(nn,0,sizeof(nn));
        memset(s,0,sizeof(s));
        int tot=0;
        int tmp=2;
        ansg=0;
        for(int i=1;i<=tt;++i)
        {
            scanf("%s",ss[i]);
            nn[i]=strlen(ss[i]);
            nn[0]=-1;
            for(int t=0;t<nn[i];++t)s[tot++]=ss[i][t];
            nn[i]+=nn[i-1]+(i==tt?0:1);
            if(i!=tt)s[tot++]=tmp++;
        }
        nn[tt]++;
        int n=strlen(s);
        da(n+1,maxf);
        geth(n);
        k=(tt)/2+1;
        int l=0,r=n+1,mid;
        while(l!=r)
        {
            mid=(l+r+1)>>1;
            if(can(mid,n,0))  l=mid;
            else      r=mid-1;
        }
        if(l==0){printf("?");goto dd;}
        can(l,n,1);
        for(int i=1;i<=ansg;++i)
        {
            if(i!=1)
            {
	            bool flag=0;
	            for(int t=0;t<l;++t)if(s[ll[i]+t]!=s[ll[i-1]+t]){flag=1;break;}
	            if(!flag)continue;
            }
            for(int t=ll[i];t<=ll[i]+l-1;++t)putchar(s[t]);
            printf("\n");
        }
        dd:;
    }
}

SPOJ220 破译进攻计划

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 2e5+500;
const int maxf = 255;
int sa[N],rank[N],wa[N],wb[N],wv[N],h[N],tong[N],nn[N];
char s[N],ss[13][15031];
int inq[13],maxq[13],minq[13];
int tt,num;
bool use[13];
bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int n,int m)
{
    int i,j,p,*x=wa,*y=wb;
    for(i=0;i<m;++i)tong[i]=0;
    for(i=0;i<n;++i)tong[x[i]=s[i]]++;
    for(i=1;i<m;++i)tong[i]+=tong[i-1];
    for(i=n-1;i>=0;i--)sa[--tong[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,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<m;++i)tong[i]=0;
        for(i=0;i<n;++i)tong[wv[i]=x[y[i]]]++;
        for(i=1;i<m;++i)tong[i]+=tong[i-1];
        for(i=n-1;i>=0;--i)sa[--tong[wv[i]]]=y[i];
        for(swap(x,y),x[sa[0]]=0,i=1,p=1;i<n;++i)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}
void geth(int n)
{
    int i,j,k=0;
    for(i=1;i<=n;++i)rank[sa[i]]=i;
    for(i=0;i<n;h[rank[i++]]=k)
    for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
}
bool can(int ans,int n)
{
    int tot=0;
    for(int i=1;i<=n;++i)
    {
        if(h[i]<ans)
        {
            tot=0;
            memset(inq,0,sizeof(inq));
            memset(maxq,0,sizeof(maxq));
            memset(minq,0x3f,sizeof(minq));
            memset(use,0,sizeof(use));
        }
        else
        {
            for(int t=1;t<=num;++t)if(nn[t-1]<sa[i]&&sa[i]<=nn[t])
            {
                inq[t]++;
                minq[t]=min(minq[t],sa[i]);
                maxq[t]=max(maxq[t],sa[i]);
                if(maxq[t]-minq[t]>=ans&&!use[t])tot++,use[t]=true;
                if(tot==num)return 1;
            }
            for(int t=1;t<=num;++t)if(nn[t-1]<sa[i-1]&&sa[i-1]<nn[t])
            {
                inq[t]++;
                minq[t]=min(minq[t],sa[i-1]);
                maxq[t]=max(maxq[t],sa[i-1]);
                if(maxq[t]-minq[t]>=ans&&!use[t])tot++,use[t]=true;
                if(tot==num)return 1;
            }
        } 
    }
    return 0;
}
int main()
{
//  freopen("RelevantPhrasesofAnnihil.in","r",stdin);
//  freopen("RelevantPhrasesofAnnihil.out","w",stdout);
    nn[0]=-1;
    scanf("%d",&tt);
    while(tt--)
    {
        memset(inq,0,sizeof(inq));
        memset(wa,0,sizeof(wa));
        memset(wb,0,sizeof(wb));
        memset(wv,0,sizeof(wv));
        memset(sa,0,sizeof(sa));
        memset(rank,0,sizeof(rank));
        memset(h,0,sizeof(h));
        scanf("%d",&num);
        int tot=0,qiguaizifu=2;
        for(int i=1;i<=num;++i)
        {
            scanf("%s",ss[i]);
            nn[i]=strlen(ss[i]);
        }
        for(int i=1;i<=num;++i)
        {
            for(int t=0;t<nn[i];++t)
            s[tot++]=ss[i][t];
            s[tot++]=qiguaizifu++;
        }
        for(int i=1;i<=num;++i)nn[i]+=(nn[i-1]+1);
        int n=strlen(s);
        da(n+1,maxf);
        geth(n);
        int l=0,r=(n+1)/2;
        while(l!=r)
        {
            int mid=l+r+1>>1;
            if(can(mid,n))  l=mid;
            else      r=mid-1;
        }
        printf("%d\n",l);
    }
}

POJ1226 Substrings

暂略。