最近在看后缀数组，刚开始看完后，自己写个后缀数组的倍增算法都累死了(ps:lz太菜了)，慢慢写了几道之后好多了。
poj 1743:
题目求最长不想交子字符串，
方法是二分长度k求上限，然后根据k把height数组分组，每组字符串间的公共长度大于=k,然后对于每个组，如果sa[i]的最大值和最小值相差大于k，那么就存在两个子字符串不相交，这个k就满足题意。
#include<cstring>
#include<cstdio>
int n;
int wa[20010],wb[20010],ws[20010],rank[20010],sa[20010],wv[20010],height[20010],r[20010];
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 *x=wa,*y=wb,*t;
int i,j,p;
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;m=p,j*=2)
{
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++)ws[i]=0;
for(i=0;i<n;i++)wv[i]=x[y[i]];
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,i=1,x[sa[0]]=0,p=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void cal(int *r,int *sa,int n)
{
int j;
for(int i=1;i<=n;i++)rank[sa[i]]=i;
int k=0;
for(int 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 x)
{
int man=-1;
int minn=30000;
for(int i=0;i<n;i++)
{
if(height[i]>=x)
{
if(man<sa[i])man=sa[i];
if(minn>sa[i])minn=sa[i];
if(man-minn>=x)return 1;
}
else
{
man=minn=sa[i];
}
}
return 0;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==0)break;
n--;
int j,k;
scanf("%d",&j);
for(int i=0;i<n;i++)
{
scanf("%d",&k);
r[i]=k-j+100;
j=k;
}
r[n]=0;
da(r,sa,n+1,200);
cal(r,sa,n);
int l=1,r=n/2;
while(l<r)
{
int m=(l+r+1)>>1;
if(check(m))l=m;
else
r=m-1;
}
if(l>=4)
printf("%d\n",l+1);
else
printf("0\n");
}
}
spoj694:
题目要求所有不同的子字符串，首先还是求后缀数组，每个长度为k的后缀包含k个子字符串，然后从i=1->n计算每个后缀可以提供多少个与前面不相同的子字符串，
很明显是
n-sa[i]-height[i]，最后减去的height[i]表示与rank排名前一个后缀的最长公共长度，所以又height[i]个子字符串重复了，所以，减掉，答案就是把这些值加起来即可。
#include<cstdio>
#include<cstring>
#define maxn 1010
int T,l,wa[maxn],sa[maxn],wb[maxn],r[maxn],n,ws[maxn],height[maxn],rank[maxn];
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 *x=wa,*y=wb,*t;
int i,j,p;
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<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[y[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++;
}
}
void cal(int *r,int *sa,int n)
{
int i,j;
for(i=1;i<=n;i++)rank[sa[i]]=i;
int k=0;
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 main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",str);
n=strlen(str);
l=0;
for(int i=0;i<n;i++)
{
r[i]=(int)str[i];
}
r[n]=0;
da(r,sa,n+1,200);
cal(r,sa,n);
for(int i=1;i<=n;i++)
{
int k=n-sa[i]-height[i];
if(k>0)l+=k;
}
printf("%d\n",l);
}
return 0;
}