[NOI2011]阿狸的打字机

· · 题解

[NOI2011]阿狸的打字机（AC自动机，Fail树，离线，树状数组）

写题解前先放阿狸！

题目叙述

给你若干个字符串（输入方式奇特），求一个字符串在另一个字符串中出现了几次。

题解

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxLen = 1e5 + 5, maxQue = 1e5 + 5;
int len, nbQue, tot, wordId, dfstime, ch[maxLen][26], fa[maxLen], wordPos[maxLen], fail[maxLen];
int in[maxLen], out[maxLen], ans[maxLen], cpy[maxLen][26];
char str[maxLen];
queue<int> Q;
vector<int> tree[maxLen], ask[maxLen];
struct Query {
    int mo, wenBen;
} que[maxQue];
struct Fenwick {
    int sum[maxLen];
    void Add(int pos, int val) {
        for (; pos <= tot; pos += lowbit(pos))
            sum[pos] += val;
    }
    int Pre(int pos) {
        int ret = 0;
        for (; pos; pos -= lowbit(pos)) ret += sum[pos];
        return ret;
    }
    int Query(int lEP, int rEP) {
        return Pre(rEP) - Pre(lEP - 1);
    }
} sum;
void Bfs() {
    fail[1] = 1;
    for (int son = 0; son < 26; ++son) {
        if (ch[1][son]) {
            Q.push(ch[1][son]);
            fail[ch[1][son]] = 1;
        } else
            ch[1][son] = 1;
    }
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        for (int son = 0; son < 26; ++son) {
            if (ch[now][son]) {
                Q.push(ch[now][son]);
                fail[ch[now][son]] = ch[fail[now]][son];
            } else
                ch[now][son] = ch[fail[now]][son];
        }
    }
}
void Dfs(int now) {
    in[now] = ++dfstime;
    for (auto to : tree[now])
        Dfs(to);
    out[now] = dfstime;
}
void Solve(int now) {
    sum.Add(in[now], 1);
    for (auto id : ask[now])
        ans[id] = sum.Query(in[wordPos[que[id].mo]], out[wordPos[que[id].mo]]);
    for (int son = 0; son < 26; ++son)
        if (cpy[now][son])
            Solve(cpy[now][son]);
    sum.Add(in[now], -1);
}
int main() {
    scanf("%s%d", str + 1, &nbQue);
    tot = 1;
    len = strlen(str + 1);
    int now = 1;
    for (int pos = 1; pos <= len; ++pos) {
        if ('a' <= str[pos] && str[pos] <= 'z') {
            if (!ch[now][str[pos] - 'a']) {
                ch[now][str[pos] - 'a'] = ++tot;
                fa[tot] = now;
            }
            now = ch[now][str[pos] - 'a'];
        } else if (str[pos] == 'P') wordPos[++wordId] = now;
        else now = fa[now];
    }
    memcpy(cpy, ch, sizeof(ch));
    Bfs();
    for (int i = 2; i <= tot; ++i) tree[fail[i]].push_back(i);
    Dfs(1);
    for (int i = 1; i <= nbQue; ++i) {
        scanf("%d%d", &que[i].mo, &que[i].wenBen);
        ask[wordPos[que[i].wenBen]].push_back(i);
    }
    Solve(1);
    for (int i = 1; i <= nbQue; ++i) printf("%d\n", ans[i]);
    return 0;
}

知识点