Description

小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻

找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星

人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高

低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在

其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以

他希望找到他接受到的 01 串中所有重复出现次数大于 1 的子串。但是他收到的

信号串实在是太长了，于是，他希望你能编一个程序来帮助他。

Input

输入文件的第一行是一个整数N ，代表小 P 接收到的信号串的长度。

输入文件第二行包含一个长度为N 的 01 串，代表小 P 接收到的信号串。

Output

输出文件的每一行包含一个出现次数大于1 的子串所出现的次数。输出的顺

序按对应的子串的字典序排列。

Sample Input

7

1010101

Sample Output

3

3

2

2

4

3

3

2

2

HINT

  对于 100%的数据，满足 0 <=  N     <=3000

 

这个题是bzoj权限题QvQ

于是只好自己和hzwer学长的标称对拍

其实一开始我的思路是差不多的

构造后缀数组，字典序为SA，然后随便枚举一下

只不过我忽略了一个重要的性质

使得我的效率变成了O(n^3)

然而只要用到下面这个性质，效率就只有O(n^2)：

因为子串是后缀的前缀，

而SA[i]和SA[i-1]的前height[i]位本质又是相同的，

因重复的子串在SA[i-1]已经往后扫过了

所以串SA[i]只需要判断height[i]+1位~最后一位构成的前缀能往后扩展多少即可。

原因：每个子串只出现过一次，共n^2个子串

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #define MAXN (3000+10) 5 using namespace std; 6 int wa[MAXN],wb[MAXN],wt[MAXN]; 7 char r[MAXN]; 8 int Height[MAXN],SA[MAXN],Rank[MAXN]; 9 int n,m=130; 10 11 bool cmp(int *y,int a,int b,int k)12 {13     int arank1=y[a];14     int brank1=y[b];15     int arank2=a+k>=n?-1:y[a+k];16     int brank2=b+k>=n?-1:y[b+k];17     return arank1==brank1 && arank2==brank2;18 }19 20 void Build_SA()21 {22     int *x=wa,*y=wb;23     for (int i=0;i
        
         =0;--i) SA[--wt[x[i]]]=i;27     28     for (int j=1;j<=n;j<<=1)29     {30         int p=0;31         for (int i=n-j;i
         
          =j) y[p++]=SA[i]-j;33         34         for (int i=0;i
          
           =0;--i) SA[--wt[x[y[i]]]]=y[i];38 39 m=1;swap(x,y);40 x[SA[0]]=0;41 for (int i=1;i
           
            =n) break;44 }45 }46 47 void Build_Height()48 {49 for (int i=0;i
            
             =j) ++k;73 if (k-i>1) printf("%d\n",k-i);74 }75 }76 }