【bzoj2251】[2010Beijing Wc]外星联络

2015.06.15 09:45 Mon | 26次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给定一个长度<=3000的01串,求出现超过一次的子串的出现次数,按字典序排列……

题解

把后缀数组搞出来,然后从头开始枚举,暴力找就行了。代码里也加了点注释。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[3005],p=1,q;
int sa[2][3005],rk[2][3005],v[3005],h[3005];
void mul(int k,int *sa,int *rk,int *SA,int *RK)
{
    for(int i=1;i<=n;i++) v[rk[sa[i]]]=i;
    for(int i=n;i;i--)
        if(sa[i]>k)
            SA[v[rk[sa[i]-k]]--]=sa[i]-k;
    for(int i=n-k+1;i<=n;i++) SA[v[rk[i]]--]=i;
    for(int i=1;i<=n;i++)
    RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);
}
void get_sa(int lim)
{
    for(int i=1;i<=n;i++) v[a[i]]++;
    for(int i=1;i<=lim;i++) v[i]+=v[i-1];
    for(int i=1;i<=n;i++) sa[p][v[a[i]]--]=i;
    for(int i=1;i<=n;i++) 
        rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
    for(int k=1;k<n;k<<=1,swap(p,q)) mul(k,sa[p],rk[p],sa[q],rk[q]);
    for(int j,k=0,i=1;i<=n;i++)
    {
        j=sa[p][rk[p][i]-1];
        while(a[i+k]==a[j+k]) k++;
        h[rk[p][i]]=k;if(k) k--;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%1d",&a[i]),a[i]++;
    get_sa(2);
    for(int r,i=1;i<=n;i++)
    //按顺序枚举保证了字典序从小到大,每次都是找出所有以排名为i开头的前缀
    {
        for(int j=h[i]+1;sa[p][i]+j-1<=n;j++)
        //为什么是h[i]+1呢,因为要防止和上次求的有重叠 
        {
            for(r=i+1;h[r]>=j;r++);
            if(r>i+1) printf("%d\n",r-i);
        }
    }
}```