参考自：http://blog.sina.com.cn/s/blog_64675f540100k9el.html
题目描述：
找出一个字符串中至少重复出现两次的字串的个数（重复出现时不能重叠）。
解题报告：
后缀数组即可解之。
枚举字串长度h
对于每一次的h，利用height数组，找出连续的height大于等于h的里面最左端和最右端得为之l和r。
如果l + h - 1 < r的话，说明没有重叠，答案加1.
O(n^2)复杂度。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std; #define maxn 1010
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=;i<m;i++)ws[i]=;
for(i=;i<n;i++)ws[x[i]=r[i]]++;
for(i=;i<m;i++)ws[i]+=ws[i-];
for(i=n-;i>=;i--)sa[--ws[x[i]]]=i;
for(j=,p=;p<n;j*=,m=p)
{
for(p=,i=n-j;i<n;i++)y[p++]=i;
for(i=;i<n;i++)
if(sa[i]>=j)
y[p++]=sa[i]-j;
for(i=;i<n;i++)wv[i]=x[y[i]];
for(i=;i<m;i++)ws[i]=;
for(i=;i<n;i++)ws[wv[i]]++;
for(i=;i<m;i++)ws[i]+=ws[i-];
for(i=n-;i>=;i--)sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
}
int rankk[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
int i,j,k=;
for(i=;i<=n;i++)rankk[sa[i]]=i;
for(i=;i<n;height[rankk[i++]]=k)
for(k?k--:,j=sa[rankk[i]-];r[i+k]==r[j+k];k++);
} int main()
{
char s[];
while(scanf("%s",s)!=EOF)
{
if(strcmp(s,"#")==)break;
int len=strlen(s);
int r[],sa[]; //又忘记初始化排名了
for(int i=;i<len;i++)r[i]=s[i];
r[len]=;//zui hou yi ge zui xiao ,ji shu pai xu de xu yao da(r,sa,len+,);
calheight(r,sa,len);
//mei ju chang du
int nn=len/;
int ans=,minn,maxx;
for(int i=;i<=nn;i++)
{
minn=,maxx=-;
for(int j=;j<=len;j++)
{
////有字串会被重复计算，所以不能这么写
//if(height[j]>=i)
//{
// minn=min(sa[j],sa[j-1]);
// maxx=max(sa[j],sa[j-1]);
// if(minn+i<=maxx)ans++;
//} //好好观察height数组的特性，可以这么写来避免重复计算
if(height[j]>=i)
{
minn=min(minn,min(sa[j],sa[j-]));
maxx=max(maxx,max(sa[j],sa[j-]));
}
else
{
if(minn+i<=maxx)ans++;
minn=,maxx=-;
}
}
if(minn+i<=maxx)ans++;
}
printf("%d\n",ans);
}
return ;
}