BZOJ2434 - [Noi2011]阿狸的打字机

2017/03/24

我好菜啊 _(:з」∠)_

一口气学会了 AC自动机。

题目描述

给定 N 个小写字符串,询问 M 次,每次两个数 ,求标号为 的字符串在 中出现了多少次。

做法

考虑全体串构成的 AC 自动机。

这时问题为:

自动机上 Root -> j 链上所有元素有多少可以通过 fail 链走到 i。

把所有的 fail 指针取反构成一个 fail 树。

问题转化为:

自动机上 Root -> j 链上所有元素有多少在 i 的子树下。

这个问题可以通过dfs序 + 树状数组统计来做。

大概过程如下: + 进入一个点 j 时,在树状数组上单点修改 BIT[L[j]] += 1
+ 处理所有形如 (i, j) 的询问,只需要查询 SUM[L[i], R[i]]
+ 退出一个点 j 时,在树状数组上单点修改 BIT[L[j]] -= 1

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define mkpr make_pair
using namespace std;

const int PSIZ = 4E5;

struct tgno {
    int u, v; tgno *n;
} POOL[PSIZ], QOOL[PSIZ]; int ppos;
tgno *Head[PSIZ], *QHead[PSIZ];

void addEdge(int u, int v) {
    POOL[ppos].v = v; POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

int L[PSIZ], R[PSIZ]; int tick = 0;
void dfs(int cur) {
    L[cur] = ++tick;
    for(tgno* i=Head[cur];i;i=i->n) {
        dfs(i->v);
    }
    R[cur] = ++tick;
}

int BIT[PSIZ];
void add(int x,int val) {
    for(int i=x;i<=tick;i+=i&-i) BIT[i]+=val;
}

int sum(int x) {
    int sum=0;
    for(int i=x;i;i-=i&-i) sum+=BIT[i];
    return sum;
}

int Ans[PSIZ];

namespace acauto {
    struct trno {
        int pos; trno *next[26], *fail, *fa;
    } POOL[PSIZ]; int ppos = 1;
    trno* s2nod[PSIZ]; int spos = 1;
    trno *root = &POOL[0];

    void mkAc() { memset(POOL, 0, sizeof(POOL)); ppos = 1; }

    inline trno* mkNod(trno* fa = NULL) {
        POOL[ppos].fa = fa;
        POOL[ppos].pos = ppos;
        return &POOL[ppos++];
    }

    void insert(char *buf) {
        trno *cur = root;
        for(int pos=0;buf[pos];pos++) {
            int cc = buf[pos] - 'a';
            if(buf[pos] == 'P') {
                s2nod[spos++] = cur;
            } else if(buf[pos] == 'B') {
                cur = cur->fa;
            } else {
                if(!cur->next[cc]) cur->next[cc] = mkNod(cur);
                cur = cur->next[cc];
            }
        }
    }

    void genFail() {
        queue<pair<trno*, char> > Q;
        for(int i=0;i<26;i++)
            if(root->next[i]) Q.push(mkpr(root->next[i], i));
        while(!Q.empty()) {
            trno* cur = Q.front().first; int k = Q.front().second; Q.pop();
            trno* fafl = cur->fa->fail;
            while(fafl && !fafl->next[k]) fafl = fafl->fail;
            cur->fail = fafl ? fafl->next[k] : root;

            for(int i=0;i<26;i++)
                if(cur->next[i]) Q.push(mkpr(cur->next[i], i));
        }
    }

    void solve(char *buf) {
        trno* cur = root; int id = 0;
        add(L[0], 1);
        for(int pos=0;buf[pos];pos++) {
            int cc = buf[pos] - 'a';
            if(buf[pos] == 'P') {
                id++;
                for(tgno* i=QHead[id];i;i=i->n) {
                    int t = s2nod[i->v]->pos;
                    Ans[i->u] = sum(R[t]) - sum(L[t]-1);
                }
            } else if(buf[pos] == 'B') {
                add(L[cur->pos], -1); cur = cur->fa;
            } else {
                cur = cur->next[cc];
                add(L[cur->pos], 1);
            }
        }
    }
};

const int OPSIZ = 2E5;
char buf[OPSIZ];

int main() {
    scanf("%s", buf);
    acauto :: insert(buf);
    acauto :: genFail();

    for(int i=1;i<acauto::ppos;i++) {
        addEdge(acauto::POOL[i].fail->pos, i);
    }

    dfs(0);

    int M; scanf("%d", &M);
    int u, v;
    for(int i=0;i<M;i++) {
        scanf("%d %d", &u, &v);
        QOOL[i].v = u;
        QOOL[i].u = i;
        QOOL[i].n = QHead[v];
        QHead[v] = &QOOL[i];
    }

    acauto :: solve(buf);

    for(int i=0;i<M;i++) {
        printf("%d\n", Ans[i]);
    }
}