2251. [2010Beijing Wc]外星联络【后缀数组】

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个子串

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define MAXN (3000+10)

 using namespace std;

 int wa[MAXN],wb[MAXN],wt[MAXN];

 char r[MAXN];

 int Height[MAXN],SA[MAXN],Rank[MAXN];

 int n,m=; 

 bool cmp(int *y,int a,int b,int k)

 {

     int arank1=y[a];

     int brank1=y[b];

     int arank2=a+k>=n?-:y[a+k];

     int brank2=b+k>=n?-:y[b+k];

     return arank1==brank1 && arank2==brank2;

 }

 void Build_SA()

 {

     int *x=wa,*y=wb;

     for (int i=;i<m;++i) wt[i]=;

     for (int i=;i<n;++i) wt[x[i]=r[i]]++;

     for (int i=;i<m;++i) wt[i]+=wt[i-];

     for (int i=n-;i>=;--i) SA[--wt[x[i]]]=i;

     for (int j=;j<=n;j<<=)

     {

         int p=;

         for (int i=n-j;i<n;++i) y[p++]=i;

         for (int i=;i<n;++i) if (SA[i]>=j) y[p++]=SA[i]-j;

         for (int i=;i<m;++i) wt[i]=;

         for (int i=;i<n;++i) wt[x[y[i]]]++;

         for (int i=;i<m;++i) wt[i]+=wt[i-];

         for (int i=n-;i>=;--i) SA[--wt[x[y[i]]]]=y[i];

         m=;swap(x,y);

         x[SA[]]=;

         for (int i=;i<n;++i)

             x[SA[i]]=cmp(y,SA[i],SA[i-],j)?m-:m++;

         if (m>=n) break;

     }

 }

 void Build_Height()

 {

     for (int i=;i<n;++i) Rank[SA[i]]=i;

     Height[]=;

     int k=;

     for (int i=;i<n;++i)

     {

         if (!Rank[i]) continue;

         if (k) k--;

         int j=SA[Rank[i]-];

         while (r[i+k]==r[j+k]) ++k;

         Height[Rank[i]]=k;

     }

 }

 int main()

 {

     scanf("%d%s",&n,r);

     Build_SA();

     Build_Height();

     for (int i=;i<n-;++i)

     {

         for (int j=Height[i]+;j<=n-SA[i];++j)//这里非常的妙啊

         {

             int k=i+;

             while (Height[k]>=j) ++k;

             if (k-i>) printf("%d\n",k-i);

         }

     }

 }

秒客网