【LuoguP4770】[NOI2018] 你的名字

布满荆棘的人生 2021-09-29 21:42 281阅读 0赞

[题目链接][Link 1]

# 题意简述 #

给定一个串 \\(S\\)  
多组询问 , 每次给定一个串 \\(T\\) 和一个 区间 \\(\[l,r\]\\)  
求串\\(T\\) 有多少个**本质不同的子串** 满足不是 \\(S\[l...r\]\\) 的子串

# Sol #

首先显然要么 \\(SAM\\) 要么 \\(SA\\)。  
这种带区间还要求本质不同的的一般用 \\(SAM\\) 好做些吧。

先考虑每次询问的区间就是整个串我们怎么做。  
考虑先补集转换，即先求出不合法的子串，然后用总的本质不同子串数减去这个值得到答案。

那么对 \\(S\\) 和 \\(T\\) 分别建立 \\(SAM\\)  
之后我们直接拿着 \\(T\\) 在 \\(S\\) 上面跑， 对于每一个点记录它最长能够匹配上的长度，这样对于一个点来说，我们知道它表示的串的区间长度，并且由于后缀自动机的性质每一个串只会被一个节点表示，那么假设这个串能识别的串长为 \\(\[l,r\]\\) ，它最长能够匹配的长度是 \\(L\\) 的话 ，贡献就是 \\(max(0,L-l)\\)

如何求出最长匹配长度?  
当我们失配的时候同时让 \\(T\\) 上的点也往上跳直到符合匹配长度，那么这个时候这个点以及它的祖先都可以用这个匹配长度更新。  
我们先把值打在一个点上，最后每个点子树内取个 \\(max\\) 就行了。

然后考虑询问的是区间怎么办。  
我们只需要知道当前转移合不合法就行了，直接线段树合并出 endpos 集合，然后在 \\(S\\) 的 \\(SAM\\) 上走的时候判一下是否能够有一个串在询问区间内就行了。

有一个坑点是当我们的串区间超过的时候不能直接跳到父亲，因为可能你要求匹配的长度太长了，所以应该一点点把长度减小，当到了父亲的长度的时候再跳上去。

#include<bits/stdc++.h> using namespace std; #define Set(a,b) memset(a,b,sizeof(a)) #define Copy(a,b) memcpy(a,b,sizeof(a)) template<class T>inline void init(T&x){ x=0;char ch=getchar();bool t=0; for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48); if(t) x=-x;return; }typedef long long ll; const int N=5e5+10; const int MAXN=N<<2; const int MAXM=MAXN*30; char S[N],T[N];int ans[MAXN]; int rt[MAXN];int ls[MAXM],rs[MAXM],size[MAXM]; bool tp;int cnt=0; #define MID (l+r)>>1 inline void Insert(int&u,int l,int r,int p){ u=++cnt;size[u]=1;if(l==r) return; int mid=MID;if(mid>=p) Insert(ls[u],l,mid,p);else Insert(rs[u],mid+1,r,p); } inline int Merge(int u,int v,int l,int r){ if(!u||!v) return u|v;int p=++cnt; size[p]=size[u]+size[v]; if(l==r) return p;int mid=MID; ls[p]=Merge(ls[u],ls[v],l,mid); rs[p]=Merge(rs[u],rs[v],mid+1,r); return p; } inline int Find(int u,int l,int r,int L,int R){ if(!u||L>R||!size[u]) return 0;if(l==r) return l;int mid=MID; if(l>=L&&r<=R) { if(size[rs[u]]) return Find(rs[u],mid+1,r,L,R); return Find(ls[u],l,mid,L,R); } if(mid>=R) return Find(ls[u],l,mid,L,R); if(mid< L) return Find(rs[u],mid+1,r,L,R); int pos=0; if(size[rs[u]]) pos=Find(rs[u],mid+1,r,mid+1,R); if(!pos) pos=Find(ls[u],l,mid,L,mid); return pos; } struct SAM{ int son[MAXN][26],fa[MAXN],len[MAXN];int n;int cnt=0,lst,id[MAXN],ws[MAXN];ll difnum=0; inline void Clear(){while(~cnt) {Set(son[cnt],0),fa[cnt]=len[cnt]=ws[cnt]=id[cnt]=0,ans[cnt]=0,--cnt;}lst=cnt=0;fa[0]=-1;} inline void extend(int c){ int u=lst;int p=lst=++cnt;len[p]=len[u]+1;if(tp==1) Insert(rt[p],1,n,len[p]); while(~u&&!son[u][c]) son[u][c]=p,u=fa[u]; if(~u) { int v=son[u][c];if(len[v]==len[u]+1) {fa[p]=v;return;} int q=++cnt;Copy(son[q],son[v]);fa[q]=fa[v];len[q]=len[u]+1;fa[v]=fa[p]=q; while(~u&&son[u][c]==v) son[u][c]=q,u=fa[u]; }return; } inline void build(char*S,int l){Clear();fa[0]=-1;n=l;for(int i=1;i<=l;++i) extend(S[i]-'a');return;} inline void Prework(){ difnum=0;for(int i=1;i<=cnt;++i) difnum+=len[i]-len[fa[i]]; for(int i=1;i<=cnt;++i) ++ws[len[i]];for(int i=1;i<=n;++i) ws[i]+=ws[i-1];for(int i=cnt;i;--i) id[ws[len[i]]--]=i; return; } inline ll Calc(){ ll Ans=difnum; for(int i=cnt;i;--i) {int u=id[i];ans[fa[u]]=max(ans[fa[u]],ans[u]);ans[u]=min(ans[u],len[u]);if(ans[u]>len[fa[u]]) Ans-=ans[u]-len[fa[u]];} return Ans; } inline void Tree_Build(){for(int i=cnt;i;--i) {int u=id[i];rt[fa[u]]=Merge(rt[fa[u]],rt[u],1,n);}} }samS,samT; int lS; inline bool check(int u,int l,int r,int len){int R=Find(rt[u],1,lS,l,r);if(R-len+1<l) return 0;return 1;} int main() { scanf("%s",S+1);tp=1; samS.build(S,strlen(S+1));samS.Prework(); samS.Tree_Build();tp=0;lS=strlen(S+1); int Q;init(Q); for(int i=1;i<=Q;++i){ scanf("%s",T+1); int l,r;init(l),init(r); int len=strlen(T+1); samT.build(T,len);samT.Prework(); int u=0,v=0,nowL=0; for(int j=1;j<=len;++j) { int c=T[j]-'a'; while(~u&&(!samS.son[u][c]||!check(samS.son[u][c],l,r,nowL+1))) if(--nowL<=samS.len[samS.fa[u]]) u=samS.fa[u];//... 要一点一点减 , 减到了才跳 , 不然会判挂 !! if(nowL<0) nowL=0; if(~u&&samS.son[u][c]) {u=samS.son[u][c],v=samT.son[v][c];++nowL;} else u=0,nowL=0,v=0; while(v&&samT.len[samT.fa[v]]>=nowL) v=samT.fa[v]; if(v) ans[v]=max(ans[v],nowL); } ll Ans=samT.Calc(); printf("%lld\n",Ans); } return 0; }

转载于:https://www.cnblogs.com/NeosKnight/p/10650788.html

[Link 1]: https://www.luogu.org/problemnew/show/P4770