【bzoj2434】 [Noi2011]阿狸的打字机

2015.02.01 14:56 Sun | 6次阅读 | 旧日oi | 固定链接 | 源码

Description

 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。
经阿狸研究发现,这个打字机是这样工作的:
l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。
l 按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。
例如,阿狸输入aPaPBbP,纸上被打印的字符如下:
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

Input

 输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m,表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。

Output

 输出m行,其中第i行包含一个整数,表示第i个询问的答案。

Sample Input

aPaPBbP
3
1 2
1 3
2 3

Sample Output

2
1
0

HINT

 1<=N<=10^5
1<=M<=10^5
输入总长<=10^5

题解

真是一道好题……自从学了ac自动机之后根本没怎么练,这次就相当于重新学了一遍……
首先建立trie树,在碰到P时维护ed[x]=++idx以及id[idx]=x,前者表示终点为x的打印串的编号,后者表示第idx个打印串的末尾节点为x,相反的两个东西;碰到‘B’时返回当前节点的父亲节点。最后建出来的树从根出发到每一个ed[x]!=0的节点都代表着一个打印串
接下来建ac自动机,建法没什么特殊的,就是要顺便建出一颗fail树,fail树是什么呢?就是把每个节点的fail指针连一条边指向这个节点形成的一棵树,这棵树有一个特点,就是一个节点的所有子节点代表的串的后缀都包含这个节点代表的串,这个性质十分有用。因为我们要求的就是一个a串在另一个b串中出现的次数,b串中的节点在a串的最后一个节点的子树中出现过几次,b串就包含几个a串,如何统计次数,可以用到树状数组,先把fail树搜索出一个dfs序,变成区间的形式。每搜到一个字母,就在它在fail树种代表区间的首节点+1。碰到‘B'则减一。碰到“P”的时候,处理所有跟当前打印串有关的询问。一些细节问题看代码吧。
我就是非指针版的爱好者。。感谢ygy同学,http://blog.csdn.net/Vmurder/article/details/42875307

我的程序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
#define maxn 100005
#define T 26
struct fail{
    struct edge{
        int to;
        int next;
    }e[maxn];
    int h[maxn],tp;
    void ae(int u,int v)
    {
        e[++tp].to=v;e[tp].next=h[u];h[u]=tp;
    }
    int st[maxn],ed[maxn],dfn;
    void dfs(int u=0)
    {
        st[u]=++dfn;
        for(int i=h[u];i;i=e[i].next)
        dfs(e[i].to);
        ed[u]=dfn;
    }
}Fail;
struct BIT{
    int c[maxn<<1];
    int lowbit(int x)
    {
        return x&(-x);
    }
    inline void add(int x,int y)
    {
        for(x=Fail.st[x];x<(maxn<<1);x+=lowbit(x))
        c[x]+=y;
    }
    inline int query(int x)
    {
        int ret=0;
        for(int i=Fail.ed[x];i;i-=lowbit(i)) ret+=c[i];
        for(int i=Fail.st[x]-1;i;i-=lowbit(i)) ret-=c[i];
        return ret;
    }
}bit;
struct Trie{
    int pa[maxn],next[maxn][T],fail[maxn];
    int ed[maxn],id[maxn];
    int root,cnt,idx;
    int m,a,b;
    char str[maxn];
    void insert()
    {
        scanf("%s",str);
        for(int alp,x=0,i=0;str[i];i++)
        {
            if(str[i]=='P') ed[x]=++idx,id[idx]=x;
            else if(str[i]=='B') x=pa[x];
            else{
                alp=str[i]-'a'; 
                if(!next[x][alp]) next[x][alp]=++cnt,pa[cnt]=x;
                x=next[x][alp];
            }
        }
    }
    void build()
    {
        queue<int> q;
        q.push(0);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int temp,v,i=0;i<T;i++)
            if(v=next[u][i])
            {
                if(!u) fail[v]=0;
                else {
                    temp=fail[u];
                    while(temp&&!next[temp][i]) temp=fail[temp];
                    fail[v]=next[temp][i];
                }
                q.push(v);
                Fail.ae(fail[v],v);
            }
        }
    }
    struct edge{
        int to;
        int next;
    }e[maxn];
    int h[maxn],tp;
    void ae(int u,int v)
    {
        e[++tp].to=v;e[tp].next=h[u];h[u]=tp;
    }
    void input()
    {
        cnt=0;cin>>m;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            ae(b,a);
        }
    }
    int ans[maxn];
    void query(int u)
    {
        for(int i=h[u];i;i=e[i].next)
        ans[i]=bit.query(id[e[i].to]);
    };
    void work()
    {
        for(int x=0,i=0;str[i];i++)
        {
            if(str[i]=='P') query(ed[x]);
            else if(str[i]=='B') bit.add(x,-1),x=pa[x];
            else{
                x=next[x][str[i]-'a'];
                bit.add(x,1);
            }
        }
    }
    void output()
    {
        for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    }
}trie;
int main()
{
    trie.insert();
    trie.build();
    Fail.dfs();
    trie.input();
    trie.work();
    trie.output();
    return 0;
}```