题意：给一个字符串。输出在原串中出现次数大于1的子串的出现次数。这些本质不同的子串按字典序大小排序输出次数。

一眼题？嗯。、后缀数组就行了、根据sa数组和height数组扫一遍。前后扫height数组。

反正n≤3000，没必要二分了。还要写rmq啥的多麻烦啊是吧、、然后就行了、感觉跑的蛮快的？

第一次加了fread和fwrite还变慢了、、

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=2000005;
int tmp1[maxn],tmp2[maxn],cs[maxn],cv[maxn],rank[maxn],height[maxn],sa[maxn];
char s[maxn],str[maxn];
inline bool cmp(int *r,int a,int b,int l){
    return  r[a]==r[b] && r[a+l]==r[b+l];
}inline void da(char *r,int *sa,int n,int m){
    int i,j,p,*x=tmp1,*y=tmp2,*t;
    for(i=0;i<m;i++)cs[i]=0;
    for(i=0;i<n;i++)cs[x[i]=r[i]]++;
    for(i=1;i<m;i++)cs[i]+=cs[i-1];
    for(i=n-1;i>=0;i--)sa[--cs[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,m=p){
        for(p=0,i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<n;i++)cv[i]=x[y[i]];
        for(i=0;i<m;i++)cs[i]=0;
        for(i=0;i<n;i++)cs[cv[i]]++;
        for(i=1;i<m;i++)cs[i]+=cs[i-1];
        for(i=n-1;i>=0;i--)sa[--cs[cv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}inline void ch(char *r,int n){
    int i,j,k=0;
    for(i=0;i<n;i++)rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
        for(k=max(k-1,0),j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}int main(){
    int n;  scanf("%d%s",&n,str);
    for(int i=0;i<n;i++)str[i]++;   str[n++]=0;
    da(str,sa,n,256);   ch(str,n);
    for(int i=1;i<n;i++){
        for(int j=height[i]+1;sa[i]+j<n;j++){
            int l,r;
            for(l=i;l>=0 && height[l]>=j;l--);
            for(r=i+1;r<=n && height[r]>=j;r++);
            if(r-l<=1)continue;
            printf("%d\n",r-l);
        }
    }return 0;
}

• 相关文章