常見操作：先把所有串都連到一起，但中間加上一個特殊的符號（不能在原串中/出現過）作為分割

由于全部的子串就等于所有后綴的所有前綴，那我們對于每一個后綴，去求一個最長的前綴，來滿足這個前綴在至少K個原串中出現過

那我們就二分一下這個前綴的長度。現在的問題就是怎么判斷這個前綴是否在K個串中出現過了。

顯然，對于一個后綴s的長度為x的前綴，只要某個后綴t 和s的LCP>=x，就說明x也是t的后綴

我們知道，LCP(x,y)=min{height[rank[y]],height[rank[y]-1],...,height[rank[x]+1]}，所以其實t和s的LCP也是單調的，滿足條件的是一個排名區間

那我們用二分出來這個區間的左右端點（用st表預處理一下height的區間最小值），然后只要判斷這個區間里的后綴是否滿足出現在K個串中就可以了

我們只要提前處理出來left[i]，表示一個最大的排名，使得sa[left[i]]...sa[i]在不同串中出現次數>=K，然后判斷我剛二分出來的那個區間[l,r]，是否l<=left[r]就可以了

復雜度$O(nlog^2n)$，據說有點卡常，那稍微優化一下

我們第一次二分前綴的長度的時候，顯然現在在做的的最大的長度一定是>=(上一個后綴的最大前綴長度-1)的，所以只要像求height那樣推著做就可以了

據說均攤復雜度O(nlogn)

（第一次寫后綴數組各種懵...最后還是全都照著大佬的題解抄的...）

1 #include<bits/stdc++.h> 2 #define pa pair<int,int> 3 #define ll long long 4 using namespace std; 5 const int maxn=2e5+10; 6 7 inline ll rd(){ 8 ll x=0;char c=getchar();int neg=1; 9 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();} 10 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 11 return x*neg; 12 } 13 14 int NN,N,M,K; 15 char ch[maxn]; 16 int suf[maxn],rank[maxn],rank1[maxn],cnt[maxn],tmp[maxn]; 17 int h[maxn],left0[maxn],bel[maxn],st[maxn][20],pos[maxn][2]; 18 19 inline void getsuf(){ 20 int i,j,k;M=126; 21 for(i=1;i<=N;i++) cnt[ch[i]]=1; 22 for(i=1;i<=M;i++) cnt[i]+=cnt[i-1]; 23 for(i=N;i;i--) rank[i]=cnt[ch[i]]; 24 for(k=1;j!=N;k<<=1){ 25 memset(cnt,0,sizeof(cnt)); 26 for(i=1;i<=N;i++) cnt[rank[i+k>N?0:i+k]]++; 27 for(i=1;i<=M;i++) cnt[i]+=cnt[i-1]; 28 for(i=N;i;i--) tmp[cnt[rank[i+k>N?0:i+k]]--]=i; 29 memset(cnt,0,sizeof(cnt)); 30 for(i=1;i<=N;i++) cnt[rank[i]]++; 31 for(i=1;i<=M;i++) cnt[i]+=cnt[i-1]; 32 for(i=N;i;i--) suf[cnt[rank[tmp[i]]]--]=tmp[i]; 33 memcpy(rank1,rank,sizeof(rank)); 34 rank[suf[1]]=j=1; 35 for(i=2;i<=N;i++){ 36 int ipk=suf[i]+k>N?0:suf[i]+k,i1pk=suf[i-1]+k>N?0:suf[i-1]+k; 37 if(rank1[ipk]!=rank1[i1pk]||rank1[suf[i]]!=rank1[suf[i-1]]) j++; 38 rank[suf[i]]=j; 39 }M=j; 40 } 41 for(i=1;i<=N;i++) suf[rank[i]]=i; 42 } 43 44 inline void geth(){ 45 //h[1]=1; 46 for(int i=1,j=0;i<=N;i++){ 47 if(rank[i]==1) continue; 48 if(j) j--; 49 int x=suf[rank[i]-1]; 50 while(i+j<=N&&x+j<=N&&ch[i+j]==ch[x+j]) j++; 51 h[rank[i]]=j; 52 } 53 } 54 55 inline void getleft0(){ 56 int n=0; 57 memset(cnt,0,sizeof(cnt)); 58 for(int i=1,j=1;i<=N;i++){ 59 if(ch[suf[i]]=='z'+1) continue; 60 if(!cnt[bel[suf[i]]]) n++; 61 cnt[bel[suf[i]]]++; 62 if(n>=K){ 63 for(;n-(cnt[bel[suf[j]]]==1)>=K;n-=(cnt[bel[suf[j++]]]==0)) cnt[bel[suf[j]]]--; 64 left0[i]=j; 65 } 66 } 67 } 68 69 inline void getst(){ 70 for(int i=N;i;i--){ 71 st[i][0]=h[i]; 72 for(int j=1;st[i+(1<<(j-1))][j-1];j++){ 73 st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); 74 } 75 } 76 } 77 78 inline int rmq(int l,int r){ 79 int k=log2(r-l+1); 80 return min(st[l][k],st[r-(1<<k)+1][k]); 81 } 82 83 inline bool check(int p,int x){ 84 int l,r,l0,r0; 85 if(h[p+1]<x) r0=p; 86 else{ 87 l=p+1;r=N; 88 while(l<=r){ 89 int m=(l+r)>>1; 90 if(rmq(p+1,m)>=x)r0=m,l=m+1; 91 else r=m-1; 92 } 93 } 94 if(h[p]<x) l0=p; 95 else{ 96 l=2;r=p; 97 while(l<=r){ 98 // printf("%d %d\n",l,r); 99 int m=(l+r)>>1; 100 if(rmq(m,p)>=x) l0=m,r=m-1; 101 else l=m+1; 102 }l0--; 103 } 104 return left0[r0]>=l0; 105 } 106 107 inline void solve(){ 108 for(int i=1;i<=NN;i++){ 109 int k=0;ll ans=0; 110 for(int j=pos[i][0];j<pos[i][1];j++){ 111 if(k) k--; 112 for(;j+k<pos[i][1]&&check(rank[j],k+1);k++); 113 ans=ans+k; 114 } 115 printf("%lld ",ans); 116 }printf("\n"); 117 } 118 119 120 121 int main(){ 122 //freopen("3277.in","r",stdin); 123 // freopen("aa.out","w",stdout); 124 int i,j,k; 125 N=NN=rd(),K=rd(); 126 for(i=1,j=1;i<=N;i++){ 127 pos[i][0]=j; 128 scanf("%s",ch+j);k=strlen(ch+j); 129 ch[j+k]='z'+1; 130 for(int t=j;t<j+k;t++) bel[t]=i; 131 j=j+k+1; 132 pos[i][1]=j-1; 133 }N=j-1; 134 getsuf(); 135 geth(); 136 getleft0(); 137 getst(); 138 solve(); 139 return 0; 140 }

?

轉載于:https://www.cnblogs.com/Ressed/p/9677823.html

總結

以上是生活随笔為你收集整理的bzoj3277 串 (后缀数组+二分答案+ST表)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。