题意简述

给定一个串 \(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;

}

巴特西

【LuoguP4770】[NOI2018] 你的名字

题意简述

Sol

最新文章

热门文章