首页 > 代码库 > BZOJ 2251: [2010Beijing Wc]外星联络

BZOJ 2251: [2010Beijing Wc]外星联络

Description

一个01串,求每个出现次数大于1的次数,\(n\leqslant 10^5\)

Solution

后缀数组。

枚举子串,他扩展的时候左端点单增,右端点单减,然后统计一下就行了...

复杂度\(O(n^2)\)

Code

/**************************************************************    Problem: 2251    User: BeiYu    Language: C++    Result: Accepted    Time:648 ms    Memory:1392 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; const int N = 3050; int n,m=2;char str[N];int a[N]; namespace SA {    int t1[N],t2[N],c[N],sa[N],rk[N],ht[N];         void get_sa(int a[],int n=::n,int m=::m) {        int *x=t1,*y=t2;        for(int i=1;i<=m;i++) c[i]=0;        for(int i=1;i<=n;i++) c[x[i]=a[i]]++;        for(int i=1;i<=m;i++) c[i]+=c[i-1];        for(int i=n;i;--i) sa[c[x[i]]--]=i;        for(int k=1,p=0;k<n;k<<=1,p=0) {            for(int i=n-k+1;i<=n;i++) y[++p]=i;            for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;            for(int i=1;i<=m;i++) c[i]=0;            for(int i=1;i<=n;i++) c[x[i]]++;            for(int i=1;i<=m;i++) c[i]+=c[i-1];            for(int i=n;i;--i) sa[c[x[y[i]]]--]=y[i];            swap(x,y),x[sa[1]]=p=1;            for(int i=2;i<=n;i++)                 x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;            if(p>=n) break;m=p;        }    }    void get_ht(int a[],int n=::n) {        for(int i=1;i<=n;i++) rk[sa[i]]=i;        for(int i=1,j,k=0;i<=n;ht[rk[i++]]=k)             for(j=sa[rk[i]-1],k=k?k-1:k;a[i+k]==a[j+k];k++);    }} int mi[N]; int main() {    scanf("%d",&n);    scanf("%s",str+1);    for(int i=1;i<=n;i++) a[i]=str[i]-‘0‘+1;    using namespace SA;    get_sa(a,n,m);    get_ht(a,n);//  for(int i=1;i<=n;i++) cout<<sa[i]<<" ";cout<<endl;//  for(int i=1;i<=n;i++) cout<<ht[i]<<" ";cout<<endl;/*  for(int i=1;i<=n;i++)        for(int j=ht[i]+1;sa[i]+j-1<=n;j++)        {            int l,r;            for(l=i;l>=1&&ht[l]>=j;l--);            for(r=i+1;r<=n&&ht[r]>=j;r++);            if(r-l>1)printf("%d\n",r-l);        }*/    for(int i=1;i<=n;i++) {        int l,r;        mi[i]=ht[i];        for(l=i-1;l;l--) mi[l]=min(ht[l],mi[l+1]);        mi[i]=n;        for(r=i+1;r<=n;r++) mi[r]=min(ht[r],mi[r-1]);        mi[i]=ht[i];        l=1,r=n;//      for(int j=1;j<=n;j++) cout<<mi[j]<<" ";cout<<endl;        for(int j=ht[i]+1;sa[i]+j-1<=n;j++) {            for(;mi[l]<j && l<=i;l++);            for(;mi[r]<j && r>=i+1;r--);//          cout<<j<<" "<<l<<" "<<r<<endl;            if(max(0,i-l+1)+max(0,r-i)+1>1)                printf("%d\n",max(0,i-l+1)+max(0,r-i)+1);        }    }return 0;}

  

BZOJ 2251: [2010Beijing Wc]外星联络