題目傳送門

題意：對一個字符串求一個最長的子串使得它至少出現(xiàn)k次

額，因?yàn)檫@個題目呢，他的字符集非常大(100W)

所以直接用SAM是不行了，我們考慮用離散化+SA，讓后就可以分塊rmq了

當(dāng)然這樣很麻煩，我們還是用SAM，但是兒子集合用map來存，這樣空間就是O(n)的，時間多了一個log

#pragma GCC opitmize("O3") #pragma G++ opitmize("O3") #include<map> #include<stdio.h> #include<string.h> #include<algorithm> #define N 40005 using namespace std; map<int,int> s[N]; int mx[N],sz[N],f[N],ans=0; int n,m,lst=1,cnt=1,v[N],r[N]; inline int extend(int c){int p=lst,np=lst=++cnt,q,nq;mx[np]=mx[p]+1; sz[np]=1;for(;p&&!s[p][c];p=f[p]) s[p][c]=np;if(!p) return f[np]=1;q=s[p][c];if(mx[q]==mx[p]+1) f[np]=q;else{nq=++cnt;mx[nq]=mx[p]+1;f[nq]=f[q]; f[q]=f[np]=nq;s[nq]=s[q];for(;p&&s[p][c]==q;p=f[p]) s[p][c]=nq;} } int main(){scanf("%d%d",&n,&m);for(int x,i=1;i<=n;++i,extend(x)) scanf("%d",&x);for(int i=1;i<=cnt;++i) ++v[mx[i]];for(int i=1;i<=n;++i) v[i]+=v[i-1];for(int i=cnt;i;--i) r[v[mx[i]]--]=i;for(int i=cnt;i;--i){sz[f[r[i]]]+=sz[r[i]];if(sz[r[i]]>=m) ans=max(ans,mx[r[i]]);}printf("%d\n",ans); }

轉(zhuǎn)載于:https://www.cnblogs.com/Extended-Ash/p/9477186.html

總結(jié)

以上是生活随笔為你收集整理的Poj3261 Milk Patterns的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。