【BZOJ-2251】外星联络后缀数组 + 暴力

2251: [2010Beijing Wc]外星联络

Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 670 Solved: 392
[Submit][Status][Discuss]

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

Source

Solution

后缀数组..套路求完SA,height后暴力一下

求一个字串出现的次数，只要从该字串第一次出现的时候暴力往后匹配即可

所以枚举排名为i的起点,从height[i]+1开始算就好了...至于为什么要+1,如果直接从height开始算.SA[i]和SA[i-1]开头的串会重复计算,所以要+1

Code

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

#define maxn 3010

char S[maxn];int SA[maxn],N;

int wa[maxn],wb[maxn],ws[maxn],wv[maxn];

int cmp(int *r,int a,int b,int l)

{

    return r[a]==r[b]&&r[a+l]==r[b+l];

}

void DA(char *r,int *sa,int n,int m)

{

    int p,*x=wa,*y=wb,*t;

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

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

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

    for (int i=n-; i>=; i--) sa[--ws[x[i]]]=i;

    p=; for (int j=; p<n; j*=,m=p)

        {

            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<n; i++) wv[i]=x[y[i]];

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

            for (int i=; i<n; i++) ws[wv[i]]++;

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

            for (int i=n-; i>=; i--) sa[--ws[wv[i]]]=y[i];

            t=x,x=y,y=t;p=;x[sa[]]=;

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

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

        }

}

int rank[maxn],height[maxn];

void calheight(char *r,int *sa,int n)

{

    int k=;

    for (int i=; i<=n; i++) rank[sa[i]]=i;

    for (int i=; i<n; height[rank[i++]]=k)

        {k?k--:;for (int j=sa[rank[i]-]; r[i+k]==r[j+k]; k++);}

}

int main()

{

    scanf("%d",&N); scanf("%s",S);

    for (int i=; i<N; i++) S[i]=S[i]-''+; S[N]=;

    DA(S,SA,N+,); calheight(S,SA,N);

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

        for (int j=height[i]+; SA[i]+j-<=N; j++)

            {

                int l,r;

                for (l=i; height[l]>=j&&l>=; l--);

                for (r=i+; height[r]>=j&&r<=N; r++);

                if (r-l>) printf("%d\n",r-l);

            }

    return ;

}

悲伤的故事..手误打错一个字符...WA成狗还一直没看出来....最后气急败坏重新敲了一遍1A了...

【BZOJ-2251】外星联络后缀数组 + 暴力-LMLPHP

外星