Lvat_s Blog

考虑维护可持久化线段树+字典树

首先建出两个字典树(一正一反)，求一下dfs序然后就变成了查询当前字符串在这两个字典树中区间的共有值

我们可以利用可持久化线段树来支持查询

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2005,M=2000005;

int n,ans,len,posA[N],posB[N],root[N*25],l[N*25],r[N*25],v[N*25],cnt,en,h[M],m;
char s[M],ch;

inline void Read_Decrypt(){
while((ch=getchar())<'a' || ch>'z');
s[len=1]=(ch-'a'+ans)%26;
while((ch=getchar())>='a' && ch<='z')s[++len]=(ch-'a'+ans)%26;
}

struct Edge{
int b,next;
}e[N];

inline void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}

struct Trie{
int son[M][26],cnt,dfn,st[M],ed[M];
inline int ins0();
inline int ins1();
void dfs(int x);
inline pair<int,int> ask0();
inline pair<int,int> ask1();
}A,B;

inline int Trie::ins0(){
int x=0;
for(int i=1;i<=len;i++){
	if(!son[x][s[i]])son[x][s[i]]=++cnt;
	x=son[x][s[i]];
}
return x;
}

inline int Trie::ins1(){
int x=0;
for(int i=len;i;i--){
	if(!son[x][s[i]])son[x][s[i]]=++cnt;
	x=son[x][s[i]];
}
return x;
}

void Trie::dfs(int x){
st[x]=++dfn;
for(int i=0;i<26;i++)if(son[x][i])dfs(son[x][i]);
ed[x]=dfn;
}

inline pair<int,int> Trie::ask0(){
int x=0;
for(int i=1;i<=len;i++){
	if(!son[x][s[i]])return make_pair(0,0);
	x=son[x][s[i]];
}
return make_pair(st[x],ed[x]);
}

inline pair<int,int> Trie::ask1(){
int x=0;
for(int i=len;i;i--){
	if(!son[x][s[i]])return make_pair(0,0);
	x=son[x][s[i]];
}
return make_pair(st[x],ed[x]);
}

inline int Insert(int x,int a,int b,int p){
int y=++cnt;v[y]=v[x]+1;
if(a==b)return y;
int mid=a+b>>1;
if(p<=mid)l[y]=Insert(l[x],a,mid,p),r[y]=r[x];
else l[y]=l[x],r[y]=Insert(r[x],mid+1,b,p);
return y;
}

inline int Query(int x,int a,int b,pair<int,int> p){
if(!x)return 0;
if(p.first<=a && b<=p.second)return v[x];
int mid=a+b>>1,ans=0;
if(p.first<=mid)ans+=Query(l[x],a,mid,p);
if(p.second>mid)ans+=Query(r[x],mid+1,b,p);
return ans;
}

int main(){
freopen("3483.in","r",stdin);
freopen("3483.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    Read_Decrypt();
    posA[i]=A.ins0();posB[i]=B.ins1();
}
A.dfs(0);B.dfs(0);
for(int i=1;i<=n;i++)AddEdge(A.st[posA[i]],B.st[posB[i]]);
for(int i=1;i<=A.dfn;i++){
	root[i]=root[i-1];
	for(int j=h[i];j;j=e[i].next)root[i]=Insert(root[i],1,B.dfn,e[j].b);
}
scanf("%d",&m);
while(m--){
    pair<int,int> L,R;
    Read_Decrypt();
    L=A.ask0();
    Read_Decrypt();
    R=B.ask1();
    if(L.first && R.first)ans=Query(root[L.second],1,B.dfn,R)-Query(root[L.first-1],1,B.dfn,R);
    else ans=0;
    printf("%d\n",ans);
}
return 0;
}