传送门：http://www.spoj.com/problems/REPEATS/

思路：又是一道论文题。

论文上是这么说的

这题用到了枚举长度的方法，往后匹配我们只要看两个后缀的LCP即可，而往前匹配，一个显然的做法是把串反过来，接到后面看对应的后缀的LCP。实际上并不需要这样，我们只需要看它还差几个字符就可以是循环次数加1，那我们就往前移这么多位，看这两个后缀的LCP长度是否足够，足够就加1（最多也只会加1,因为如果加2，那么这个答案就会被上一次枚举统计过了。）

#include
#include
#include
#include
const int maxn=100010;
using namespace std;
int T,n,t1[maxn],t2[maxn],sum[maxn],rank[maxn],sa[maxn],st[maxn][20],h[maxn],maxs;char s[maxn],c[5];void getsa(){memset(sum,0,sizeof(sum));int *x=t1,*y=t2,m=255,p=0;for (int i=1;i<=n;i++) sum[x[i]=s[i]]++;for (int i=1;i<=m;i++) sum[i]+=sum[i-1];for (int i=n;i;i--) sa[sum[x[i]]--]=i;for (int j=1;pj) y[++p]=sa[i]-j;memset(sum,0,sizeof(sum));for (int i=1;i<=n;i++) sum[x[y[i]]]++;for (int i=1;i<=m;i++) sum[i]+=sum[i-1];for (int i=n;i;i--) sa[sum[x[y[i]]]--]=y[i];swap(x,y),x[sa[1]]=p=1;for (int i=2;i<=n;i++){if (y[sa[i]]!=y[sa[i-1]]||y[sa[i]+j]!=y[sa[i-1]+j]) p++;x[sa[i]]=p;}}memcpy(rank,x,sizeof(rank));
}void geth(){for (int i=1,j=0;i<=n;i++){if (rank[i]==1) continue;while (s[i+j]==s[sa[rank[i]-1]+j]) j++;h[rank[i]]=j;if (j) j--;}
}void getst(){for (int i=1;i<=n;i++) st[i][0]=h[i];for (int j=1;j<=19;j++)for (int i=1;i+(1<r) swap(l,r);l++;int k=log2(r-l+1);//一定要记得++lreturn min(st[l][k],st[r-(1<=0&&getmin(k,k+i)>=i) tmp++;//大于等于i是因为如果长度足够(i-tmp%i)，那么这两个串后面都会匹配了，所以这是没有影响的。maxs=max(maxs,tmp+1);}printf("%d\n",maxs);}return 0;
}