题目链接 ： https://www.acwing.com/problem/content/description/142/
Hash + 二分
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 7; typedef unsigned long long ull; const ull mod = 131; ull p[maxn],h[maxn]; int sa[maxn],rank[maxn],height[maxn]; char str[maxn]; int n ; ull get(int x,int y){ return h[y] - h[x - 1] * p[y - x + 1]; } int lcp(int x,int y){ int l = 0 ,r = min(n - x + 1,n - y + 1); while(l < r){ int mid = (l + r + 1) >> 1; if(get(x,x + mid - 1) != get(y,y + mid - 1)) r = mid - 1; else l = mid; } return l; } bool cmp(int x , int y){ int l = lcp(x,y); int av = x + l > n ? INT_MIN : str[x + l]; int bv = y + l > n ? INT_MIN : str[y + l]; return str[x + l] < str[y + l]; } int main(){ scanf("%s",str + 1); n = strlen(str + 1); p[0] = 1; for(int i = 1;i <= n ;i ++){ p[i] = mod * p[i-1]; h[i] = mod * h[i-1] + str[i] - '0' + 1; sa[i] = i; } sort(sa + 1, sa + 1 + n , cmp); for(int i = 2;i <= n ;i ++){ height[i] = lcp(sa[i],sa[i-1]); } for(int i = 1;i <= n ;i ++) printf("%d%c",sa[i]-1," "[i==n]); printf("0 "); for(int i = 2;i <= n ;i ++) printf("%d%c",height[i]," "[i==n]); return 0; }
后缀数组
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 7; struct DA{ bool cmp(int *r,int a,int b,int l){ return r[a]==r[b]&&r[a+l]==r[b+l]; } int t1[maxn],t2[maxn],c[maxn]; int rank[maxn],height[maxn],RMQ[maxn],mm[maxn]; int best[20][maxn]; int r[maxn]; int sa[maxn]; int str[maxn]; void da(int n,int m){ n++; int i,j,p,*x=t1,*y=t2; for(i=0;i<m;i++)c[i]=0; for(i=0;i<n;i++)c[x[i]=str[i]]++; for(i=1;i<m;i++)c[i]+=c[i-1]; for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i; for(j=1;j<=n;j<<=1){ p=0; for(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<m;i++)c[i]=0; for(i=0;i<n;i++)c[x[y[i]]]++; for(i=1;i<m;i++)c[i]+=c[i-1]; for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; if(p>=n)break; m=p; } int k=0; n--; for(i=0;i<=n;i++)rank[sa[i]]=i; for(i=0;i<n;i++){ if(k)k--; j=sa[rank[i]-1]; while(str[i+k]==str[j+k])k++; height[rank[i]]=k; } } void initRMQ(int n){ for(int i=1;i<=n;i++)RMQ[i]=height[i]; mm[0]=-1; for(int i=1;i<=n;i++) mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; for(int i=1;i<=n;i++)best[0][i]=i; for(int i=1;i<=mm[n];i++) for(int j=1;j+(1<<i)-1<=n;j++){ int a=best[i-1][j]; int b=best[i-1][j+(1<<(i-1))]; if(RMQ[a]<RMQ[b])best[i][j]=a; else best[i][j]=b; } } int askRMQ(int a,int b){ int t; t=mm[b-a+1]; b-=(1<<t)-1; a=best[t][a];b=best[t][b]; return RMQ[a]<RMQ[b]?a:b; } int lcp(int a,int b){ a=rank[a];b=rank[b]; if(a>b)swap(a,b); return height[askRMQ(a+1,b)]; } void print(int n){ // cout<<"sa[] "; for(int i=2;i<=n;i++)cout<<sa[i]<<" ";cout<<endl; // cout<<"rank[] "; // for(int i=2;i<=n;i++)cout<<rank[i]<<" ";cout<<endl; //cout<<"height[] "; for(int i=2;i<=n;i++)cout<<height[i]<<" ";cout<<endl; } }AA,BB; //n=8; //* num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ }; 注意 num 最后一位为 0，其他 大于 0 //*rank[] = 4, 6, 8, 1, 2, 3, 5, 7, 0 ;rank[0 n-1] 为有效值，rank[n] 必定为 0 无效值 // *sa[] = 8, 3, 4, 5, 0, 6, 1, 7, 2 ;sa[1 n] 为有效值，sa[0] 必定为 n 是 无效值 //*height[]= 0, 0, 3, 2, 3, 1, 2, 0, 1 ;height[2 n] 为有效值 int main(int argc, char const *argv[]) { string str; cin >> str; for(int i = 0;i < str.size();i ++) AA.str[i] = str[i] - '0' + 100; AA.str[str.size()] = 0; AA.da(str.size() + 1,600); AA.print(str.size() + 1); return 0; }