正題

題目鏈接:https://www.luogu.com.cn/problem/P4022

---

題目大意

給出$m$個(gè)模板串。

然后$n$次詢問給出一個(gè)串$S$要求找到一個(gè)最大的$L$使得能夠?qū)?span id="ze8trgl8bvbq" class="katex--inline">$S$超過$90\%$的部分拿出來分后每個(gè)串都是某個(gè)模板串的子串且長度不小于$L$。

所有輸入文件長度不超過 $1100000$ 字節(jié)。字符集為$\{0,1\}$

---

解題思路

先把模板串拿出來構(gòu)一個(gè)廣義SAM，然后考慮用這個(gè)對串進(jìn)行匹配。

先對于每個(gè)位置求出一個(gè)$le{n}_i$表示一個(gè)最長的長度使得$i$的后綴是某個(gè)模板串的子串。

然后考慮二分一個(gè)$L$后進(jìn)行$dp$。

那么有
$$f_i=max\{f_{i?1},f_j+i?j\}(j\in [i?le{n}_i,i?L))$$

因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$i?le{n}_i$單調(diào)所以把$j$丟進(jìn)單調(diào)隊(duì)列里就好了。

時(shí)間復(fù)雜度$O(n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1200000; int n,m,cnt,f[N],q[N],ml[N]; int ch[N][2],len[N],fa[N]; char s[N]; int Insert(int p,int c){if(ch[p][c]){int q=ch[p][c];if(len[p]+1==len[q])return q;else{int nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;return nq; }}int np=++cnt;len[np]=len[p]+1;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;if(!p)fa[np]=1;else{int q=ch[p][c];if(len[p]+1==len[q])fa[np]=q;else{int nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=fa[np]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;}}return np; } bool check(int L,int n){int head=1,tail=0,ans=0;for(int i=1;i<=n;i++){if(i>=L){int j=i-L;while(head<=tail&&f[j]-j>f[q[tail]]-q[tail])tail--;q[++tail]=j;}while(head<=tail&&q[head]<i-ml[i])head++;f[i]=0;if(head<=tail)f[i]=f[q[head]]+i-q[head];f[i]=max(f[i],f[i-1]);ans=max(ans,f[i]);}return (ans*10>=n*9); } int main() {scanf("%d%d",&n,&m);cnt=1;for(int i=1;i<=m;i++){scanf("%s",s+1);int l=strlen(s+1),x=1;for(int j=1;j<=l;j++)x=Insert(x,s[j]-'0');}while(n--){scanf("%s",s+1);int sl=strlen(s+1),x=1,L=0;for(int i=1;i<=sl;i++){int c=s[i]-'0';while(x&&!ch[x][c]){x=fa[x];L=len[x];}if(x)x=ch[x][c],L++;else x=1,L=0;ml[i]=L;}int l=1,r=sl;while(l<=r){int mid=(l+r)>>1;if(check(mid,sl))l=mid+1;else r=mid-1;}printf("%d\n",r);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4022-[CTSC2012]熟悉的文章【广义SAM,dp,单调队列】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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