正題

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

---

題目大意

給出兩個字符串$s,t$。$q$次給出$l,r$詢問$s_{l～r}$與$t$的最長公共子串。

---

解題思路

對于末尾的條件很好做，直接上$SAM$就好了，設$f_i$表示一個最大的數滿足$s_{i?f_i+1,i}$是$t$的子串。

然后對于一個詢問$l,r$就是相當于求$max\{min\{f_{l+i?1},i\}\}(i\in [1,r?l+1])$這個東西。

考慮二分一個答案$x$，那么在$[l,l+x?2]$這個范圍內一定不會有答案，在剩下的$[l+x?1,r]$內取一個最大值和$x$做一下對比即可去掉$min$的條件。

用一個$ST$維護一下就好了，時間復雜度$O(n+q\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=4e5+10,T=19; int n,m,q,last,cnt,lg[N],f[N][T]; int ch[N][26],len[N],fa[N]; char s[N],t[N]; void Insert(int c){int p=last,np=last=++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; } int Ask(int l,int r){int z=lg[r-l+1];return max(f[l][z],f[r-(1<<z)+1][z]); } int main() {scanf("%s",t+1);m=strlen(t+1);scanf("%s",s+1);n=strlen(s+1);scanf("%d",&q);last=cnt=1;for(int i=1;i<=n;i++)Insert(s[i]-'a');for(int i=1,p=1,l=0;i<=m;i++){int c=t[i]-'a';while(!ch[p][c])p=fa[p],l=len[p];if(!p)p=1,l=0;else p=ch[p][c],l++;f[i][0]=l;}for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);while(q--){int L,R;scanf("%d%d",&L,&R);int l=1,r=R-L+1;while(l<=r){int mid=(l+r)>>1;if(Ask(L+mid-1,R)>=mid)l=mid+1;else r=mid-1;}printf("%d\n",r);}return 0; }

總結

以上是生活随笔為你收集整理的P6640-[BJOI2020]封印【SAM,二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

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