小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻 找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星 人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高 低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在 其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以 他希望找到他接受到的 01 串中所有重复出现次数大于 1 的子串。但是他收到的 信号串实在是太长了，于是，他希望你能编一个程序来帮助他。
输入文件的第一行是一个整数N ，代表小 P 接收到的信号串的长度。 输入文件第二行包含一个长度为N 的 01 串，代表小 P 接收到的信号串。
输出文件的每一行包含一个出现次数大于1 的子串所出现的次数。输出的顺 序按对应的子串的字典序排列。
对于 100%的数据，满足 0 <= N <=3000
【分析】
脑洞大开...手玩玩出了正解...
狂暴切到了40ms...本来想优化优化看能不能再快个4ms...最后放弃了
首先我们将字符串的sa搞出来，然后以sa的从小到大排序做一个O(n^2)的算法，给大家介绍一下手玩步骤...
以001001为栗，做完后缀数组后，有如下按字典序排好顺序的后缀
001
001001
01
001
1
1001
设立一个指针i从1到n扫描，对于每个i，再有一个j从i+1到n扫描
对于001和001001，height[2]=3。
对于001001和01，height[3]=1。
我们惊奇地发现height变了...那么此时对答案的贡献有(height[2]-height[3])个2 (2=j-i+1)，也就是00和001对答案产生贡献，把两个2扔到栈里面。
然后继续扫到001，height[4]=1，扫到1，height[5]=0，那么子串0又对答案产生了一个4的贡献，把4扔到栈里面。
然后把栈中元素一个一个输出来(字典序，先进后出，因为0的字典序<01和001的字典序)
问题又来了...
比如0101010
排序后
010
01010
0101010
...
在i==1时，做完一遍j的扫描，我们已经把010的贡献统计了，那么在i==2时，还要统计一遍可怎么办。
很简单...只要搞出来s[i]和s[i-1]的lcp的长度（程序里面的cnt）即可。
如果height在更新后<cnt了，那就不能计入答案
【代码】
//bzoj 2251 [2010Beijing Wc]外星联络 #include<stack> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=3005; stack <int> q; char s[mxn]; int m,len,cnt,pre,now; int b[mxn],x[mxn],y[mxn],sa[mxn],rank[mxn],height[mxn]; inline bool comp(int i,int j,int l) { return y[i]==y[j]&&(i+l>len?-1:y[i+l])==(j+l>len?-1:y[j+l]); } inline void work() { int i,j,k,p;m=128; fo(i,0,m) b[i]=0; fo(i,1,len) b[x[i]=s[i]]++; fo(i,1,m) b[i]+=b[i-1]; for(i=len;i>=1;i--) sa[b[x[i]]--]=i; for(k=1;k<=len;k<<=1) { p=0; fo(i,len-k+1,len) y[++p]=i; fo(i,1,len) if(sa[i]>k) y[++p]=sa[i]-k; fo(i,0,m) b[i]=0; fo(i,1,len) b[x[y[i]]]++; fo(i,1,m) b[i]+=b[i-1]; for(i=len;i>=1;i--) sa[b[x[y[i]]]--]=y[i]; swap(x,y),p=2,x[sa[1]]=1; fo(i,2,len) x[sa[i]]=comp(sa[i-1],sa[i],k)?p-1:p++; if(p>len) break; m=p; } p=k=0; fo(i,1,len) rank[sa[i]]=i; for(i=1;i<=len;height[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++); } int main() { int i,j,k,l,r; scanf("%d",&len); scanf("%s",s+1); work(); fo(i,1,len) { int tmp=height[i+1],cnt=0; if(!height[i+1]) continue; fo(k,0,len) if(s[sa[i]+k]==s[sa[i-1]+k]) cnt++; else break; fo(j,i+1,len) { tmp=min(tmp,height[j]); if(tmp<=cnt) break; if(height[j+1]<tmp) fo(k,1,tmp-max(cnt,height[j+1])) q.push(j-i+1); } while(!q.empty()) printf("%d\n",q.top()),q.pop(); } return 0; }