题意：一串01串，让你找出所有在串中出现过次数大于1的字串的出现次数，按照字典序输出。 明显后缀数组。。。 重复的话，我们求出height以后，求出当前height[i]对应的起点sa[i]，然后长度为height[i]，左右暴力扩展，注意这里扩展的是排名而不是下标，所以这时字串的出现次数就是扩展的距离之和了。
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e5+5; int n; int b[N],c[N],d[N],height[N],sa[N],rank[N]; char s[N]; inline void getsa(int n,int m) { fo(i,0,m)b[i]=0; fo(i,1,n)b[s[i]]++; fo(i,1,n)b[i]+=b[i-1]; fd(i,n,1)c[b[s[i]]--]=i; int t=0; fo(i,1,n) { if (s[c[i]]!=s[c[i-1]])t++; rank[c[i]]=t; } int j=1; while (j<=n) { fo(i,0,n)b[i]=0; fo(i,1,n)b[rank[i+j]]++; fo(i,1,n)b[i]+=b[i-1]; fd(i,n,1)c[b[rank[i+j]]--]=i; fo(i,0,n)b[i]=0; fo(i,1,n)b[rank[i]]++; fo(i,1,n)b[i]+=b[i-1]; fd(i,n,1)d[b[rank[c[i]]]--]=c[i]; int t=0; fo(i,1,n) { if (rank[d[i]]!=rank[d[i-1]]|| rank[d[i]]==rank[d[i-1]]&&rank[d[i]+j]!=rank[d[i-1]+j])t++; c[d[i]]=t; } fo(i,1,n)rank[i]=c[i]; if (t==n)break; j*=2; } fo(i,1,n)sa[rank[i]]=i; } inline void getheight() { int k=0; fo(i,1,n) { if (k) k--; int j=sa[rank[i]-1]; while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++; height[rank[i]]=k; } } int main() { scanf("%d",&n); scanf("%s",s+1); fo(i,1,n) { s[i]=s[i]-'0'+1; } getsa(n,2); getheight(); fo(i,1,n) for(int j=height[i]+1;sa[i]+j-1<=n;j++) { int l,r; for(l=i;l>=1&&height[l]>=j;l--); for(r=i+1;r<=n&&height[r]>=j;r++); if (r-l>1)printf("%d\n",r-l); } return 0; }