正題

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

---

解題思路

給出一個串$S$和$n$個串$T_i$。$m$次詢問$S_{a～b}$在$T_{l～r}$中出現的最多次數并且輸出這個串的編號。

$1\le |s|\le 5\times 10^5,\sum T_i\le 5\times 10^4,1\le m\le 5\times 10^5$

---

解題思路

把$S$和$T$丟一起跑一個廣義$SAM$。

兩個串包含當且僅當他們在$SAM$上對應節點是父子，所以直接對于每個節點開一個線段樹，然后$T$的每個位置對應編號加一。

對于詢問$S$子串直接倍增跳到對應位置然后用線段樹合并上來的東西求答案就好了。

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e6+2e5+10,S=19; int answ,ansv; struct SegTree{int cnt,w[N*20],v[N*20],ls[N*20],rs[N*20];void PushUp(int x,int L,int R){w[x]=-1;if(w[ls[x]]>w[x])w[x]=w[ls[x]],v[x]=max(v[ls[x]],L);if(w[rs[x]]>w[x])w[x]=w[rs[x]],v[x]=v[rs[x]];return;}void Change(int &x,int L,int R,int pos){if(!x)x=++cnt;if(L==R){w[x]++;v[x]=L;return;}int mid=(L+R)>>1;if(pos<=mid)Change(ls[x],L,mid,pos);else Change(rs[x],mid+1,R,pos);PushUp(x,L,R);return;}void Ask(int x,int L,int R,int l,int r){if(!x){if(answ<0)answ=0,ansv=l;return;}if(L==l&&R==r){if(answ<w[x])answ=w[x],ansv=v[x];return;}int mid=(L+R)>>1;if(r<=mid)Ask(ls[x],L,mid,l,r);else if(l>mid)Ask(rs[x],mid+1,R,l,r);else Ask(ls[x],L,mid,l,mid),Ask(rs[x],mid+1,R,mid+1,r);}int Merge(int x,int y,int L,int R){if(!x||!y)return x+y;int p=++cnt;if(L==R){w[p]=w[x]+w[y];v[p]=L;return p;}int mid=(L+R)>>1; ls[p]=Merge(ls[x],ls[y],L,mid);rs[p]=Merge(rs[x],rs[y],mid+1,R);PushUp(p,L,R);return p;} }T; struct node{int to,next; }a[N]; int n,m,l,tot,f[N][S+1],rt[N],ls[N]; int cnt,len[N],ch[N][26],fa[N],pos[N]; char s[N]; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } 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; } void dfs(int x){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;f[y][0]=x;dfs(y);rt[x]=T.Merge(rt[x],rt[y],1,n);}return; } int GetPos(int l,int r){int x=pos[r];for(int i=S;i>=0;i--)if(len[f[x][i]]>=r-l+1)x=f[x][i];return x; } int main() {scanf("%s",s+1);l=strlen(s+1);cnt=1;for(int i=1,x=1;i<=l;i++){x=Insert(x,s[i]-'a');pos[i]=x;}scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);int x=1,l=strlen(s+1);for(int j=1;j<=l;j++){x=Insert(x,s[j]-'a');T.Change(rt[x],1,n,i);}}for(int i=2;i<=cnt;i++)addl(fa[i],i);dfs(1);for(int j=1;j<=S;j++)for(int i=1;i<=cnt;i++)f[i][j]=f[f[i][j-1]][j-1];scanf("%d",&m);while(m--){int a,b,l,r;scanf("%d%d%d%d",&l,&r,&a,&b);int x=GetPos(a,b);answ=-1;ansv=0;T.Ask(rt[x],1,n,l,r);printf("%d %d\n",ansv,answ);}return 0; }

總結

以上是生活随笔為你收集整理的CF666E-Forensic Examination【广义SAM,线段树合并】的全部內容，希望文章能夠幫你解決所遇到的問題。

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