字符串+数据结构 AC自动机+线段树 P2414题解
Prean
·
·
题解
难不成是我后缀自动机学魔怔了，AC 自动机都能套上线段树
题意：给你一颗 Trie，每次询问两个节点 u,v ， u 代表的字符串在 v 代表的字符串中出现了多少次。
让我们思考一下字符串在 AC 自动机 上是如何匹配的：
- 跳儿子节点
- 对于每个儿子节点跳 fail，若跳到匹配串就令 ans++
差不多就是标记一个节点 u ，然后询问是否有若干个节点在该节点的子树内。
于是，当 x 相同时，就可以标记 x 的每一个前缀后，在 fail 树上做一个子树和。查询的时候直接查询子树和就好了。
不过重要的一点是：如何维护一个节点是哪些字符串的前缀。
我们发现，每次 $ B $ 跳 father 的时候，经过这个节点的字符串是连续的一段。相当于使用线段树区间修改。所以标记一下就好啦。
需要注意一点是线段树要标记永久化。
code:
```cpp
#include<cstring>
#include<cstdio>
#include<queue>
typedef unsigned uint;
const uint M=1e5+5;
uint n,m,cnt,tot,len,fa[M],pos[M],lst[M],fail[M],root[M],chi[M][26];char s[M];
uint L,R,q[M];
struct Node{
uint L,R,tag;
}t[M*50];
inline uint min(const uint&a,const uint&b){
return a-b>>31?a:b;
}
inline uint max(const uint&a,const uint&b){
return a-b>>31?b:a;
}
void Modify(uint&u,const uint&l,const uint&r,const uint&L=1,const uint&R=len){
if(l>R||L>r)return;if(!u)u=++cnt;
if(l<=L&&R<=r)return void(t[u].tag=1);
uint mid=L+R>>1;
Modify(t[u].L,l,r,L,mid);Modify(t[u].R,l,r,mid+1,R);
}
uint Query(const uint&u,const uint&x,const uint&L=1,const uint&R=len){
if(!u)return 0;if(L==R)return t[u].tag;
uint mid=L+R>>1;
if(x<=mid)return Query(t[u].L,x,L,mid)+t[u].tag;
else return Query(t[u].R,x,mid+1,R)+t[u].tag;
}
uint Merge(const uint&q,const uint&p){
if(!q||!p)return q|p;
uint u=++cnt;
t[u].L=Merge(t[q].L,t[p].L);
t[u].R=Merge(t[q].R,t[p].R);
t[u].tag=t[q].tag+t[p].tag;
return u;
}
inline void Build(){
uint i,u,c;L=1;
for(c=0;c^26;++c)if(chi[1][c])fail[q[++R]=chi[1][c]]=1;
while(L<=R){
if(!fail[u=q[L++]])fail[u]=1;
for(c=0;c^26;++c){
if(chi[u][c])fail[q[++R]=chi[u][c]]=chi[fail[u]][c];
else chi[u][c]=chi[fail[u]][c];
}
}
}
inline void init(){
uint i,u=++tot,now=1;n=strlen(s);
for(i=0;i<n;++i){
if(s[i]=='B')u=fa[u];
else if(s[i]=='P')++len;
else{
if(!chi[u][s[i]-97])fa[chi[u][s[i]-97]=++tot]=u;
u=chi[u][s[i]-97];
}
}
u=1;Build();
for(i=0;i<n;++i){
if(s[i]=='B')lst[u]^now?Modify(root[u],lst[u],now-1):void(),u=fa[u];
else if(s[i]=='P')pos[now++]=u;
else lst[u=chi[u][s[i]-97]]=now;
}
while(u^1)lst[u]^now?Modify(root[u],lst[u],now-1):void(),u=fa[u];
do root[fail[q[R]]]=Merge(root[fail[q[R]]],root[q[R]]);while(--R);
}
signed main(){
uint x,y;scanf("%s%u",s,&m);init();
while(m--)scanf("%u%u",&x,&y),printf("%u\n",Query(root[pos[x]],y));
}
```