https://www.luogu.com.cn/problem/P4770
题意
给定字符串(S),多次询问,每次给出(l,r,T)询问不在(S)的([l,r])区间出现过的(T)的本质不同的子串
前68分满足(l=1,r=n)
题解
先考虑前68分,正难则反,即求出(T)在(S)中出现的本质不同的子串
我们定义(a[i])为(T)长度为(i)的前缀在(S)中存在的最长后缀长度
求法即对(S,T)建出后缀自动机,把(T)串放到(S)串的(SAM)上匹配
然后还要自下而上的用儿子的(a)更新父亲的(a)
最终答案,对于(T)的(SAM)上的节点(i),它做出的贡献就是(len[i]-max(len[fa[i]],a[i]))
对于长度小于等于(a[i])的后缀串因为在(T)串中存在所以没有了贡献
以及(SAM)上每个点代表的本质不同的子串只有((len[fa],len[i]])这一段
最终答案:(sum_{i=1}^{cnt}len[i]-max(len[fa[i]],a[i]))
考虑100分与68分的区别在于
我们无法分离出([l,r])的(S)的(SAM),然后把(T)串放到(S)串的(SAM)上匹配
但是考虑(T)串在(S)串([l,r])上匹配的时候需要的操作
设当前匹配点为(root)
1.查询(ch[root][c])在([l,r])中是否存在
2.跳到(fa[root])
3.查询(len[root])
所以,考虑维护(endpos)集合,采用线段树合并
对于1操作就是判断该点一段区间是否有(endpos)
对于二操作,因为父节点的(endpos)是当前点的超集,所以一定合法
对于三操作,这个点的长度应该是(min(len,l-max(l,maxpos)+1))
(maxpos)为对应区间的最大(endpos)
但是我从上午打到了下午,有几个细节被恶心到了
100分和68分只有在求出(a)的部分做出了些调整
对于统计答案及其他一些地方,完全是等效的,所以我在此不再赘述
线段树合并的时候,因为要保留每个线段树节点,而过去的合并操作会毁掉合并的两颗线段树
所以要每次合并节点((x,y))都要合并给新建的新的一个节点(w)
空间复杂度(感谢左手边的带神神)如果直接线段树合并是(O(nlog))的,但是有新建节点
每次合并新建节点必定是((x,y))合并为(w)一个点,并且((x,y))不会再被合并了
所以相当于每次由2个点合并成了1个点
空间复杂度(sumlimits frac{nlog}{1}+frac{nlog}{2}+frac{nlog}{4}...=2nlog)
在匹配判断当前点某个儿子,设为(son),是否存在于([l,r])时,找到了([l,r])的最大(endpos)后还要判断是否真的存在
因为只有(endpos)的话长度小于等于(len[fa[son]])这个点也不是真实在这个区间里
所以需要判断,合法条件是(pos>l+len[fa[son]-1)
这个地方也太狗屎了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+50;
inline int rd(register int x=0,register char ch=getchar(),register int f=0){
for(;!isdigit(ch);ch=getchar()) f=ch=='-';
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-48;
return f?-x:x;
}
int n,m,lst,cnt,ptr;
int rt[N],ls[N*20],rs[N*20],mx[N*20],ret[N];
char s[N];
int NEW(int o){
++ptr;ls[ptr]=ls[o],rs[ptr]=rs[o],mx[ptr]=mx[o];
return ptr;
}
void ins(int &x,int l,int r,int p){
x=NEW(x);mx[x]=max(mx[x],p);
if(l==r) return;int mid=(l+r)>>1;
p<=mid?ins(ls[x],l,mid,p):ins(rs[x],mid+1,r,p);
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x+y;
if(l==r) return x;int mid=(l+r)>>1;
int w=NEW(x);
ls[w]=merge(ls[x],ls[y],l,mid);
rs[w]=merge(rs[x],rs[y],mid+1,r);
mx[w]=max(mx[ls[w]],mx[rs[w]]);
return w;
}
int ask(int x,int l,int r,int L,int R){
if((L<=l&&r<=R)||!x) return mx[x];
int mid=(l+r)>>1,Mx=0;
if(L<=mid) Mx=max(Mx,ask(ls[x],l,mid,L,R));
if(R>mid) Mx=max(Mx,ask(rs[x],mid+1,r,L,R));
return Mx;
}
struct SAM{
int n,lst,cnt;
int len[N],fa[N],buc[N],rk[N],id[N];
map<int,int> ch[N];
void extend(int c){
int p=lst,np=lst=++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[q]==len[p]+1) fa[np]=q;
else{
int nq=++cnt;len[nq]=len[p]+1;fa[nq]=fa[q];fa[np]=fa[q]=nq; ch[nq]=ch[q];
for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
id[++id[0]]=np;
}
void build(int m){
clear(); n=m;
for(int i=1;i<=n;++i) extend(s[i]-'a');
for(int i=1;i<=cnt;++i) buc[len[i]]++;
for(int i=1;i<=n;++i) buc[i]+=buc[i-1];
for(int i=1;i<=cnt;++i) rk[buc[len[i]]--]=i;
}
void clear(){
for(int i=0;i<=cnt;++i){
len[i]=fa[i]=buc[i]=rk[i]=id[i]=0;
ch[i].clear();
}
lst=cnt=1;
}
}F,G;
int main(){
freopen("name.in","r",stdin);
freopen("name.out","w",stdout);
scanf("%s",s+1);n=strlen(s+1);F.build(n);
for(int i=1;i<=n;++i) ins(rt[F.id[i]],1,n,i);
for(int i=F.cnt;i;--i) if(F.fa[F.rk[i]]) rt[F.fa[F.rk[i]]]=merge(rt[F.fa[F.rk[i]]],rt[F.rk[i]],1,n);
for(int T=rd(),l,r;T;--T){
scanf("%s",s+1);m=strlen(s+1);G.build(m);
l=rd(),r=rd();
int root=1,Len=0;
ll ans=0;
for(int i=1;i<=m;++i){
while(1){
if(root==0) {root=1;Len=0;break;}
int pos=ask(rt[F.ch[root][s[i]-'a']],1,n,l,r);
if(pos>=l+F.len[F.fa[F.ch[root][s[i]-'a']]]) {root=F.ch[root][s[i]-'a'];Len=min(Len+1,pos-l+1);break;}
else {root=F.fa[root];Len=min(Len,F.len[root]);}
}
ret[G.id[i]]=min(G.len[G.id[i]],Len);
}
for(int i=G.cnt;i;--i) if(G.fa[G.rk[i]]) ret[G.fa[G.rk[i]]]=min(G.len[G.fa[G.rk[i]]],max(ret[G.fa[G.rk[i]]],ret[G.rk[i]]));
for(int i=1;i<=G.cnt;++i) ans+=max(0,G.len[i]-max(G.len[G.fa[i]],ret[i]));
for(int i=0;i<=G.cnt;++i) ret[i]=0;
printf("%lld
",ans);
}
}