bzoj 2251: [Beijing Wc]外星联络

黄学长说是模板题，，然而不会。。

大概是按后缀数组的顺序（也就是字典序）来枚举一下，然后再按长度枚举一下，各种各样的暴力，，，然用在height上搞2333，不会啊

1 #include<bits/stdc++.h> 2 #define N 100005<<2 3 #define LL long long 4 #define inf 0x3f3f3f3f 5 using namespace std; 6 inline int ra() 7 { 8int x=0,f=1; char ch=getchar(); 9while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}10while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}11return x*f;12 }13 char ch[N];14 int n,k,p,q;15 int a[N],rank[2][N],sa[2][N],h[N],v[N];16 void cal_sa(int sa[N], int rank[N], int Sa[N], int Rank[N])17 {18for (int i=1; i<=n; i++) v[rank[sa[i]]]=i;19for (int i=n; i>=1; i--)20 if (sa[i]>k) Sa[v[rank[sa[i]-k]]--]=sa[i]-k;21for (int i=n-k+1; i<=n; i++) Sa[v[rank[i]]--]=i;22for (int i=1; i<=n; i++) Rank[Sa[i]]=Rank[Sa[i-1]]+(rank[Sa[i]]!=rank[Sa[i-1]] || rank[Sa[i]+k]!=rank[Sa[i-1]+k]);23 }24 void get_height()25 {26k=0;27for (int i=1; i<=n; i++)28{29 if (rank[p][i]==1) h[1]=0;30 else{31 int j=sa[p][rank[p][i]-1];32 while (a[i+k]==a[j+k]) k++;33 h[rank[p][i]]=k; 34 if (k>0) k--;35 }36}37 }38 void work()39 {40p=0,q=1;41for (int i=1; i<=n; i++) v[a[i]]++;42for (int i=1; i<=30; i++) v[i]+=v[i-1];43for (int i=1; i<=n; i++) sa[p][v[a[i]]--]=i;44for (int i=1; i<=n; i++) rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);45for (k=1; k<n; k<<=1,p^=1,q^=1) cal_sa(sa[p],rank[p],sa[q],rank[q]);46get_height();47 }48 int main()49 {50n=ra(); scanf("%s",ch+1);51for (int i=1; i<=n; i++) a[i]=ch[i]-'0'+1;52work();53for (int i=1; i<=n; i++)54 for (int j=h[i]+1; sa[p][i]+j-1<=n; j++)55 {56 int l=i,r;57 // for (l=i; l>=1 && h[l]>=j; l--);58 for (r=i+1; r<=n && h[r]>=j; r++);59 if (r-l>1) printf("%d\n",r-l);60 }61return 0;62 }