Bakser's Blog

我是逗比。

bzoj2434 fail树+dfs序列+树状数组

| Comments

AC自动机显然。
据说AC自动机上暴力能拿70,没试过。
暴力思路:判断串y中x出现了几次,实际上就是看AC自动机上y中有几个节点可以通过fail指针跳到x的末尾节点,暴力判断之。
正解其实就是加速暴力中的判断过程,用到fail树。
将fail指针反向,形成的是一个树状结构,叫做fail树,显然能通过fail指针到达节点x的节点一定在fail树中x的子树上
于是我们可以在AC自动机上从根节点向yDFS,将栈中节点打上标记,只要统计x的子树有多少个被标记就可以了。
子树显然转化为dfs序来做,统计个数只要用BIT维护前缀和然后作差就可以了。
注意题目中各个串的给出方式,它决定了各个串之间一定有前缀关系,所以建trie就可以O(N)来做,同样最后一步AC自动机上dfs也可以用同样方式直接迭代过去。

bzoj2434
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define N 100100
#define maxsize 26
#define idx(x) ((x)-'a')
typedef pair<int,int> pii;
int len=0,f[N],ch[N][maxsize],fa[N],size(1),tid[N],num,tot,fir[N],last[N],ans[N],c[N];
int flag[N];
char s[N],str[N];
vector<pii> ask[N];
vector<int>son[N];
inline void make_fail()
{
    queue<int> q;
    for(int i=0;i<maxsize;i++)
        if(ch[0][i])q.push(ch[0][i]),f[ch[0][i]]=0;
    while(!q.empty())
    {
        int x(q.front());q.pop();
        for(int i=0;i<maxsize;i++)
        {
            int u(ch[x][i]),v;
            if(!u){ch[x][i]=ch[f[x]][i];continue;}
            q.push(u);
            for(v=f[x];v&&!ch[v][i];v=f[v]);
            f[u]=ch[v][i];
        }
    }
    for(int i=1;i<size;i++)
        son[f[i]].push_back(i);
}
inline void add(int x,int delta)
{
    for(x;x<=tot;x+=(x&(-x)))
        c[x]+=delta;
}
inline int get(int x)
{
    int res(0);
    for(x;x;x-=(x&(-x)))
        res+=c[x];
    return res;
}
inline void dfs_fail_tree(int u)
{
    fir[u]=++tot;
    for(int i=0;i<son[u].size();i++)dfs_fail_tree(son[u][i]);
    last[u]=++tot;
}
int main()
{
// freopen("test.txt","r",stdin);
 scanf("%s",str);
    int n(strlen(str)),m,pos=0;size=1;
    for(int i=0;i<n;i++)
        if(str[i]=='B')pos=fa[pos];
        else if(str[i]=='P')tid[++num]=pos;
        else 
        {
            int &v=ch[pos][idx(str[i])];
            if(!v)v=size++,fa[v]=pos;
            pos=v;
        }
    make_fail();
    scanf("%d",&m);
    for(int i=0,x,y;i<m;i++)
        scanf("%d%d",&x,&y),ask[y].push_back(make_pair(x,i));
    dfs_fail_tree(0);
    pos=0;int tag(0);
    for(int i=0;i<n;i++)
        if(str[i]=='B')add(last[pos],-1),pos=fa[pos];
        else if(str[i]=='P')
        {
            tag++;
            for(int j=0;j<ask[tag].size();j++)
            {
                int t=tid[ask[tag][j].first];
                ans[ask[tag][j].second]=get(last[t])-get(fir[t]-1);
            }
        }
        else pos=ch[pos][idx(str[i])],add(last[pos],1);
    for(int i=0;i<m;i++)printf("%d\n",ans[i]);
    return 0;
}

Comments

comments powered by Disqus