[BZOJ2434/Luogu2414][NOI2011]阿狸的打字机(AC自动机,dfs序,树状数组)

发布于 2018-03-20  76 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2434/Luogu2414][NOI2011]阿狸的打字机(AC自动机,dfs序,树状数组)

Description

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

Tag

AC自动机,dfs序,树状数组

解决思路

首先,给出的操作可以构造出一棵包含所有我们需要的字符串的Trie树,在这棵Trie上构建AC自动机,考虑如何统计答案。
考虑在 AC 自动机中如何求得一个字符串在另一个中的出现次数(注意两个字符串都是 AC 自动机中的串)。可以发现,从串 y 在 Trie 中的每一个节点出发,若能从一个节点一直跳 Fail 跳到 x 串的末尾,那么 x 就在 y 中出现了一次。这提示我们统计答案似乎与 Fail 树有关,所以我们不妨把 Fail 树提出来。
把 Fail 树提出来后有什么用呢?我们再来看一看这时答案变成了什么。
对于要求 x 在 y 中出现了多少次,那么在 Fail 树中就是 y 串有多少个节点在x 串末尾节点的 fail 树的子树内(想一想为什么)。
于是我们呢就得到了更优的算法,即对于每一个询问 x,y,我们标记出 y 串的每一个节点,然后统计有多少个节点在 x 末尾节点的子树内。子树统计可以用dfs 序做到 O(1) 地统计。
但是这样还是不够,所以我们考虑把询问离线下来,当我们扫到一个字符串末尾的时候,一起回答它的所有询问。那这个扫的顺序如何确定呢?不妨再把之前构 Trie 树的操作再做一边。
这样一边走一边在 dfs 序中单点修改一个值,遇到结尾则查询,回答所有询问。

代码

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

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lowbit(x) ((x)&(-(x)))

const int maxN=400010;
const int maxM=maxN*2;
const int maxAlpha=27;
//const int inf=2147483647;

class Trie
{
public:
    int fail,fa;
    int son[maxAlpha];
};

int n,nodecnt,m;
char str[maxN];
Trie T[maxN];
int idcnt=0,Id[maxN];
int Ques[maxN],Ans[maxN];
int qcnt=0,QHead[maxN],QNext[maxM],QV[maxM];
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
int Queue[maxN];
int dfncnt=0,Dfn[maxN],Last[maxN];
int BIT[maxN];

void GetFail();
void QAdd_Edge(int u,int v);
void Add_Edge(int u,int v);
void dfs(int u);
void Modify(int pos,int key);
int Query(int l,int r);
int Sum(int pos);

int main()
{
    mem(QHead,-1);mem(Head,-1);
    //输入并建树
    scanf("%s",str+1);
    int len=strlen(str+1);
    for (int i=1,now=0;i<=len;i++)
    {
        if (str[i]=='B') now=T[now].fa;
        else if (str[i]=='P') Id[++idcnt]=now;
        else
        {
            if (T[now].son[str[i]-'a']==0)
            {
                T[now].son[str[i]-'a']=++nodecnt;
                T[nodecnt].fa=now;
            }
            now=T[now].son[str[i]-'a'];
        }
    }
    //把询问离线下来
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        QAdd_Edge(y,i);Ques[i]=x;
    }
    //构建Fail树,同时求好dfs序方便求子树和
    GetFail();
    dfs(0);
    //再做一遍构建Trie树的过程,同时在Fail树中回答询问
    for (int i=1,now=0,cnt=0;i<=len;i++)
    {
        if (str[i]=='B'){
            Modify(Dfn[now],-1);now=T[now].fa;
        }
        else if (str[i]=='P')
        {
            cnt++;
            for (int q=QHead[cnt];q!=-1;q=QNext[q])
            {
                int id=QV[q];
                int v=Id[Ques[id]];
                Ans[id]=Query(Dfn[v],Last[v]);
            }
        }
        else
        {
            now=T[now].son[str[i]-'a'];
            Modify(Dfn[now],1);
        }
    }
    for (int i=1;i<=m;i++) printf("%d\n",Ans[i]);
    return 0;
}

void GetFail()
{
    int h=0,t=0;
    for (int i=0;i<maxAlpha;i++) if (T[0].son[i]) Queue[++h]=T[0].son[i];
    while (t!=h)
    {
        int u=Queue[++t];
        for (int i=0;i<maxAlpha;i++)
            if (T[u].son[i])
            {
                T[T[u].son[i]].fail=T[T[u].fail].son[i];
                Queue[++h]=T[u].son[i];
            }
            else T[u].son[i]=T[T[u].fail].son[i];
    }
    for (int i=1;i<=nodecnt;i++) Add_Edge(T[i].fail,i);
    return;
}

void QAdd_Edge(int u,int v)
{
    qcnt++;QNext[qcnt]=QHead[u];QHead[u]=qcnt;QV[qcnt]=v;
    return;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void dfs(int u)
{
    Dfn[u]=++dfncnt;
    for (int i=Head[u];i!=-1;i=Next[i])
        dfs(V[i]);
    Last[u]=dfncnt;
    return;
}

void Modify(int pos,int key)
{
    while(pos<=dfncnt){
        BIT[pos]+=key;pos+=lowbit(pos);
    }
    return;
}

int Query(int l,int r)
{
    return Sum(r)-Sum(l-1);
}

int Sum(int pos)
{
    int ret=0;
    while(pos){
        ret+=BIT[pos];pos-=lowbit(pos);
    }
    return ret;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2434/Luogu2414][NOI2011]阿狸的打字机(AC自动机,dfs序,树状数组)


HNCJ OIer