\(\color{white}{mjt是機房模擬賽獨自切過題的唯一的人...}\)
（應本人要求刪掉惹）

---

\(Description\)

給你\(n,k\)和長為\(n\)的字符串\(s\)。一個區間\([l,r]\)是合法的，當且僅當\(s[l...r]\)能被分成\(k\)個相同的子串。求有多少個合法區間。
\(n,k\leq3\times10^5\)。

\(Solution\)

枚舉單個子串的長度\(len\)，在\(s\)上從\(1\)開始每隔\(len\)個位置放一個關鍵點，分成若干塊。
考慮相鄰\(k\)個關鍵點，以它們開頭的\(k\)個子串是否相同。如果它們兩兩之間的\(LCP\)都\(\geq len\)，顯然是合法的。考慮怎么求這\(k\)個位置的\(LCP\)。
建\(SA\)，\(LCP\)是兩兩\(rk\)之間的最小值，也就是區間\([\min\{rk\},\max\{rk\}]\)之間的最小值。用\(set\)動態維護一下，查詢\(LCP\)就是\(O(1)\)的了。
需要枚舉\(O(n\log n)\)次，這樣這部分復雜度是\(O(n\log^2n)\)。

還有左右端點在塊內的情況，也就是跨過了\(k-1\)個整塊。容易發現這\(k-1\)塊的子串一定需要是相同的。同樣用\(SA\)和\(set\)先判一下。
設左端點\(l\)在第\(p\)塊內，右端點\(r\)在\(p+k\)塊內。記\(L[p],R[p]\)分別為第\(p\)塊的左右端點，可以發現合法的\(l\)范圍是前綴\(R[p]\)與\(R[p+1]\)的最長公共后綴，可以反著建個\(SA\)求出來，設為\(a\)。同理合法\(r\)的范圍是后綴\(L[p+k]\)與\(L[p+k-1]\)的最長公共前綴，設為\(b\)（注意與\(len-1\)取\(\min\)）。
\(r\)的長度需要在\([len-a,len-1]\)之間，所以此時合法的區間個數就是\(b-len+a+1\)。
復雜度也是\(O(n\log^2n)\)。

ps: 不知道標算是啥...（好像是SAM+主席樹）這是\(\color{red}{\text{m}}\color{black}{\text{jt}}\)的做法。
這個其實和優秀的拆分差不多...但是考場都忘了啊=-=

---

#include <set> #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #define rg register #define Rev(x) (n-(x)+1) //#define gc() getchar() #define MAXIN 500000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=3e5+5;int s[N],Log[N]; char IN[MAXIN],*SS=IN,*TT=IN; struct Suffix_Array {int sa[N],rk[N],sa2[N],tm[N],ht[N],mn[19][N];inline int LCP(int l,int r){l=rk[l], r=rk[r]; if(l>r) std::swap(l,r);++l; int k=Log[r-l+1];return std::min(mn[k][l],mn[k][r-(1<<k)+1]);}inline int LCP2(int l,int r){if(l==r) return N;++l; int k=Log[r-l+1];return std::min(mn[k][l],mn[k][r-(1<<k)+1]);}void Build(int *s,int n){int *x=rk,*y=sa2,m=27;for(int i=0; i<=m; ++i) tm[i]=0;for(int i=1; i<=n; ++i) ++tm[x[i]=s[i]+1];for(int i=1; i<=m; ++i) tm[i]+=tm[i-1];for(int i=n; i; --i) sa[tm[x[i]]--]=i;for(int k=1,p=0; k<n; k<<=1,m=p,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=0; i<=m; ++i) tm[i]=0;for(int i=1; i<=n; ++i) ++tm[x[i]];for(int i=1; i<=m; ++i) tm[i]+=tm[i-1];for(int i=n; i; --i) sa[tm[x[y[i]]]--]=y[i];std::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;}for(int i=1; i<=n; ++i) rk[sa[i]]=i;ht[1]=0;for(int i=1,k=0; i<=n; ++i){if(rk[i]==1) continue;if(k) --k;int p=sa[rk[i]-1];while(i+k<=n && p+k<=n && s[i+k]==s[p+k]) ++k;ht[rk[i]]=k;}for(int i=1; i<=n; ++i) mn[0][i]=ht[i];for(int j=1; j<=Log[n]; ++j)for(int t=1<<j-1,i=n-t; i; --i)mn[j][i]=std::min(mn[j-1][i],mn[j-1][i+t]);} }sa1,sa2;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-48,c=gc());return now; }int main() {freopen("sutoringu.in","r",stdin);freopen("sutoringu.out","w",stdout);const int n=read(),K=read();register char c=gc(); while(!isalpha(c)) c=gc(); s[1]=c-'a';for(rg int i=2; i<=n; ++i) s[i]=gc()-'a', Log[i]=Log[i>>1]+1;sa1.Build(s,n), std::reverse(s+1,s+1+n), sa2.Build(s,n);LL ans=0;for(int len=1; len*K<=n; ++len){std::set<int> st;//直接新開一個 for(int t=K-1,i=1; t--; i+=len) st.insert(sa1.rk[i]);for(int t=(K-1)*len,i=t+1; i+len-1<=n; i+=len){st.insert(sa1.rk[i]);ans+=sa1.LCP2(*st.begin(),*st.rbegin())>=len;st.erase(sa1.rk[i-t]);}if(len==1) continue;std::set<int> st2;for(int t=K-1,i=len+1; t--; i+=len) st2.insert(sa1.rk[i]);for(int i=K*len+1,j=len; i<=n; i+=len,j+=len){if(sa1.LCP2(*st2.begin(),*st2.rbegin())>=len){int a=std::min(sa2.LCP(Rev(j),Rev(j+len)),len-1),b=std::min(sa1.LCP(i,i-len),len-1);//rev!ans+=std::max(0,b-len+a+1);}st2.erase(sa1.rk[j+1]), st2.insert(sa1.rk[i]);}}printf("%lld\n",ans);return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/10613052.html

總結

以上是生活随笔為你收集整理的3.27模拟赛 sutoringu(后缀数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

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