题解 P2414 【[NOI2011]阿狸的打字机】
shadowice1984 · · 题解
很好的一道题，但是入手AC自动机不要像我一样作死这道题。
不过做完这道题你对AC自动机的理解应该提升了一个层次吧
AC自动机
一种字符串自动机，作用是，当当前字符串是字典中一个字符串的前缀时，状态节点不为空
也就是说AC自动机是多模式串的KMP
那么为了构造AC自动机，我们首先要对字典建一个trie树
然后，像KMP的next一样，我们需要构造一个数组来处理失配的情况
在一般的AC自动机板子中，我们称这个数组为fail[]，fail[i]表示，我们在AC自动机
/*其实此时的AC自动机还是trie树*/上的节点i失配，应该跳到AC自动机的那一个节点
这里直接给出递推方法：对整只trie树BFS
1.根节点的所有儿子的fail=root
2.对于一个一般的节点，它的fail可以这样求得，沿着父节点的fail路径不断“向上跳”，
对于“向上跳”路径中的每一个节点，如果他有一个出边类型恰好与当前结点和当前结点的父节点的连边类型相等，那么它的fail=这条出边指向的节点
那么匹配的时候像KMP利用next一样利用fail就好了
/*当然AC自动机的真实形态是一只自动机，又称trie图，但是这道题不是trie图*/
本题题解
发现一个有趣的事实，对于AC自动机中的每一个节点，如果节点A的fail指向节点B
就会发现B对应的字符串一定在A对应的字符串中出现
/*此处强烈画一只trie自己看一看*/
利用这个性质，原题中的询问变成了
“有多少个属于Y的节点的fail指针直接或间接指向X的结束位置”
这里我们需要再跳越一小步
如果把fail指针理解成边，那么原trie树的点和fail指针形成的边，共同构成一只树
我们一般称它为fail树
现在询问变成了，在fail树中，以X结束点为根的子树中，有多少个点属于Y
可以利用dfs序，将fail树上的点映射到一个序列上
那么我们就会发现它变成了一个序列统计问题
只要钉死“属于Y的节点”这个条件我们就可以统计了
需要利用到trie树
具体来讲dfs整只trie
每d到一个点，我们就让它对应的序列点+1，回溯的时候-1；
这样做可以保证只有当前路径上的点是有值的
如果当前点是一个结束节点，那么说明每一个属于这个串的节点都已统计完毕
此时我们只需调出每一个关于这个串的询问，区间求和即可
好像可以用树状数组维护欸……
剩下的就是代码实现了，需要乱七八糟维护一堆映射
细节看代码好了
上代码~
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n=1;//注意，邻接表不支持0号节点，trie树的根编号为1
struct nod
{int num;int typ;};
queue <nod> q;
struct trie//trie树
{
int map[100010][30];int end[100010];//记录结束点
int word;//单词计数器
int fa[100010];int fail[100010];int dis[100010];//father，以及end数组的反向数组
inline int insert(int p,char c)//trie树插入
{
if(map[p][c-'a'+1]!=0)return map[p][c-'a'+1];
map[p][c-'a'+1]=++n;fa[n]=p;return n;
}
inline int back(int p){return fa[p];}//这个是为了实现打字机的'B'键
inline void ed(int p){end[p]=++word;dis[word]=p;}
inline void build()//构造fail
{
for(int i=1;i<=26;i++)
if(map[1][i]!=0)//第一层节点的特判
{nod p;p.num=map[1][i];p.typ=i;fail[p.num]=1;q.push(p);}
while(!q.empty())//bfs
{
nod now=q.front();q.pop();
if(fail[now.num]!=1)//跳fail
{
int trail=fail[fa[now.num]];
while(1)
{
if(map[trail][now.typ]!=0){trail=map[trail][now.typ];break;}
if(trail==1)break;trail=fail[trail];
}fail[now.num]=trail;
}
for(int i=1;i<=26;i++)
{if(map[now.num][i]!=0)
{nod p;p.num=map[now.num][i];p.typ=i;q.push(p);}}
}return;
}
}tr;
struct data{int v;int nxt;}edge[200010];
int cnt;int alist[100010];
inline void add(int u,int v)//存fail树
{
edge[++cnt].v=v;edge[cnt].nxt=alist[u];
alist[u]=cnt;return;
}
struct node{int v;int num;};
struct data2{node v;int nxt;}edge1[100010];
int cnt1;int alist1[100010];
inline void add1(int u,int v,int num)//存询问
{
node p;p.v=v;p.num=num;
edge1[++cnt1].v=p;edge1[cnt1].nxt=alist1[u];
alist1[u]=cnt1;return;
}
struct treearray//4行树状数组
{
int ta[200010];
inline void ub(int& x){x+=x&(-x);}
inline void db(int& x){x-=x&(-x);}
inline void c(int x,int t){for(;x<=n;ub(x))ta[x]+=t;}
inline int sum(int x){int res=0;for(;x>0;db(x))res+=ta[x];return res;}
}ta;
int dfn[100010];int size[100010];int dfu;
bool book[100010];int ans[100010];
void dfsfail(int x)//对fail树的dfs
{
dfn[x]=++dfu;
size[x]=1;book[x]=true;
int nxt=alist[x];
while(nxt)
{
int v=edge[nxt].v;
if(book[v]==false)
{dfsfail(v);size[x]+=size[v];}
nxt=edge[nxt].nxt;
}return;
}
void dfstrie(int x)//对trie的dfs
{
ta.c(dfn[x],1);
if(tr.end[x]!=0)
{
int nxt=alist1[tr.end[x]];
while(nxt)
{
node v=edge1[nxt].v;int x=tr.dis[v.v];
ans[v.num]=ta.sum(dfn[x]+size[x]-1)-ta.sum(dfn[x]-1);
nxt=edge1[nxt].nxt;
}
}
for(int i=1;i<=26;i++)
{if(tr.map[x][i]!=0){dfstrie(tr.map[x][i]);}}
ta.c(dfn[x],-1);return;
}
char mde[100010];int len;int st;int m;
int main()
{
scanf("%s",mde+1);
len=strlen(mde+1);
for(st=1;st<=len;st++){if(mde[st]!='B'&&mde[st]!='P')break;}
int p=tr.insert(1,mde[st]);
for(int i=st+1;i<=len;i++)//构造trie
{
if(mde[i]=='B'){p=tr.back(p);}
else if(mde[i]=='P'){tr.ed(p);}
else p=tr.insert(p,mde[i]);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)//离线
{
int u;int v;
scanf("%d%d",&u,&v);
add1(v,u,i);
}tr.build();//建AC自动机
for(int i=2;i<=n;i++)
{add(tr.fail[i],i);add(i,tr.fail[i]);}//建fail树
dfsfail(1);dfstrie(1);//两边dfs
for(int i=1;i<=m;i++)
{printf("%d\n",ans[i]);}
return 0;//拜拜程序~
}