AC自动机

  • AC 自动机= Trie + KMP
  • AC 自动机基于Trie，将KMP 的Border 概念推广到多模式串上。
  • AC 自动机是一种离线型数据结构，即不支持增量添加新的字符串。
  • AC 自动机常用于将字符串询问类的问题进行离线处理，也经常与各种
    DP 结合，或是补全成Trie 图。

广义border

1.推广到两个串：对于两个串S 和T，相等的p 长度的S 的后缀和T 的前缀称为一个border。

2.推广到一个字典：对于串S 和一个字典D，相等的p 长度的S 的后缀，和任意一个字典串T 的前缀称为一个border。

3.失配（Fail）指针： 对于Trie 中的每一个节点（即某个字典串的前缀），它与Trie 中所有串的最大Border 即为失配指针

ac自动机维护的是当前状态的最大后缀满足这个后缀是字典树的前缀

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
struct AC {
    static constexpr int asz = 26;
    struct Node {       // 表示Trie树的一个节点
        int len;        // 节点对应的字符串的长度
        int fail;       // 节点的后缀链接
        int mxsuf = 0;  // 后缀的恰好匹配一个完整的字典串
        bool vis = 0;   // 这个状态是不是存在子串是字典串
        array<int, asz> next;
        // 表示从当前节点到下一个节点的转换，数组大小为字母表大小
        Node() : len{0}, fail{0}, next{} {}
    };

    vector<Node> t;
    AC() { init(); }

    void init() {
        t.assign(2, Node());  // 创建两个节点，分别是根节点和伪根节点
        t[0].next.fill(1);    // 将根节点的所有next指向伪根节点
        t[0].len = -1;        // 设置根节点的len为-1
    }

    int newNode() {        // 创建一个新节点，并返回其索引
        t.emplace_back();  // 向向量t中添加一个新的Node节点
        return t.size() - 1;
    }

    int add(const string &a, char offset = 'a') {  // 向Trie树中添加字符串
        int p = 1;                                 // 从伪根节点开始
        for (auto c : a) {
            int x = c - offset;
            if (t[p].next[x] == 0) {
                t[p].next[x] = newNode();  // 创建新节点，并更新next数组
                t[t[p].next[x]].len = t[p].len + 1;
            }
            p = t[p].next[x];  // 移动到下一个节点
        }
        t[p].vis = 1;
        t[p].mxsuf = a.size();
        return p;  // 返回最后一个字符对应的节点索引
    }

    void work() {  // 构建AC自动机的后缀链接
        queue<int> q;
        q.push(1);

        while (!q.empty()) {
            int x = q.front();
            q.pop();
            t[x].vis |= t[t[x].fail].vis;
            t[x].mxsuf = max(t[x].mxsuf, t[t[x].fail].mxsuf);
            for (int i = 0; i < asz; i++) {
                if (t[x].next[i] == 0) {                  // 如果当前节点没有对应字符的转移
                    t[x].next[i] = t[t[x].fail].next[i];  // 设置为后缀链接节点的对应转移
                } else {
                    t[t[x].next[i]].fail = t[t[x].fail].next[i];  // 设置新节点的后缀链接
                    q.push(t[x].next[i]);
                }
            }
        }
    }
    int next(int p, int x) { return t[p].next[x]; }
    int next(int p, char x, char offset = 'a') { return t[p].next[(x - offset)]; }
    int fail(int p) { return t[p].fail; }  // 获取节点p的后缀链接
    int len(int p) { return t[p].len; }
    int mxsuf(int p) { return t[p].mxsuf; }  // 获取节点p的匹配的最长后缀，满足他可以与字典串的前缀
    bool vis(int p) { return t[p].vis; }
    int size() { return t.size(); }  // 获取Trie树的节点总数
};

板子：给你一个文本串 SS 和 nn 个模式串 T1∼nT_{1 \sim n}，请你分别求出每个模式串 TiT_i 在 SS 中出现的次数。

Sol：将文本串放在AC 自动机上运行，求出每个前缀匹配到AC 自动机的哪
个节点，将该节点的标记值+1。这里标记的是匹配串，下面标记的是模式串
每个字典串的出现次数等于失配树的子树内的标记总量。因此;建出fail树，在失配树上自底向上dfs推标记即可。

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
void solve() {
    AC ac;
    cin >> n;
    vector<int> id(n + 1);
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        id[i] = ac.add(s);
    }

    ac.work();
    string tt;
    int p = 1;
    cin >> tt;
    int tot = ac.size();
    vector<int> sz(tot);

    m = tt.size();
    for (int i = 0; i < m; i++) {
        int ch = tt[i] - 'a';
        p = ac.next(p, ch);
        sz[p] += 1;
        deb(p);
    }
    vector<vector<int>> e(tot);
    for (int i = 2; i < tot; i++) {
        deb(i, ac.fail(i));
        e[ac.fail(i)].push_back(i);
    }
    auto dfs = [&](auto self, int u) -> void {
        for (auto v : e[u]) {
            self(self, v);
            sz[u] += sz[v];
        }
    };
    dfs(dfs, 1);
    for (int i = 1; i <= n; i++) cout << sz[id[i]] << endl;
}

2。https://ac.nowcoder.com/acm/contest/29086/B

  • 给出一个有N 个串的字典，然后进行M 次操作：
    1. 修改操作：向字典中新增一个字典串S。
    2. 查询操作：查询所有字典串在询问串T 中的出现次数，同一个字典
      串重复出现算多次。
      1 ≤ N, M ≤ 100, 000, 输入字符串总长度不超过3000, 000。

Sol：AC自动机无法在线处理，所以考虑离线询问。先无视修改操作，只考虑查询操作：可以建出AC 自动机。

  • 然后将查询串在AC 自动机上运行，匹配到AC 自动机的一个节点时，将该节点到根的路径上终止标记个数计入答案。

  • 由于AC 自动机是离线型数据结构，即不能支持快速增删字典串，因此
    考虑到修改操作需要先离线，动态维护终止标记，使用dfs 序+ 树状数
    组快速维护每个点到根路径上的终止标记个数。

    这里说一下怎么维护的？我们需要查询的是查询串在AC自动机上走的时候faill链上有多少标记？但是这样直接做不好做，我们考虑每个终止标记只会贡献它的fail子树，所以标记字典串完成区间加，而查询是单点查。正好符合dfs序+树状数组

    debug:由于在跑ac自动机的时候字母和数字映射内部没写，外部也没有处理。现在板子加了offset，减小出错概率。不过也要惊醒这个点

    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
    void solve() {
        int n, m;
        AC ac;
        cin >> n >> m;
        vector<int> pos;
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            pos.push_back(ac.add(s));
        }
        vector<pii> q(m);
        vector<int> id(m);
        for (int i = 0; i < m; i++) {
            int x;
            string y;
            cin >> x >> y;
            q[i].fs = x, q[i].sec = y;
            if (x == 1)
                id[i] = ac.add(y);
        }
        ac.work();
        int tot = ac.size() - 1;
        vector<vector<int>> e(tot + 1);
        for (int i = 2; i <= tot; i++) e[ac.fail(i)].push_back(i);
        int idx = 0;
        vector<int> l(tot + 1), r(tot + 1);
        auto dfs = [&](auto self, int u) -> void {
            l[u] = ++idx;
            for (auto v : e[u]) {
                self(self, v);
            }
            r[u] = idx;
        };
        dfs(dfs, 1);
        Fwk<int> fw(tot + 2);
        for (auto x : pos) {
            deb(l[x], r[x]);
            fw.add(l[x], 1);
            fw.add(r[x] + 1, -1);
        }
        for (int i = 0; i < m; i++) {
            auto [x, y] = q[i];
            if (x == 1) {
                fw.add(l[id[i]], 1);
                fw.add(r[id[i]] + 1, -1);
            } else {
                int p = 1;
                int res = 0;
                for (auto it : y) {
                    p = ac.next(p, it-'a'), res += fw.sum(l[p]);
                }
                cout << res << endl;
            }
        }
    }

    $\sum_{v是u的祖先}(i-len(v)+1) \times (len(询问串)-i+1) $

3.给出一个字典，至多包含300, 000 个字典串，且字典串总长度不超过
300, 000。
再给出一个文本串T(|T| ≤ 300, 000)，问最少使用多少个字典串可以拼
接出T。同一个字典串使用多次算多次。
拼接时允许重叠，只需要保证重叠部分匹配即可，例如T = abcd，可以
使用字典串S = cdxx 拼接成T′ = abcdxx。

Sol:首先比较容易想到使用DP：f[i] 表示拼接出T[1, i] 的操作次数.
转移时，设某字典串Si 等于T[1, i] 的后缀，会导致如下转移：
f[i]=min(f[i−1],f[i−2],⋅⋅⋅,f[i−∣Si∣]])+1f[i] = min(f[i − 1], f[i − 2], · · · , f[i − |Si|]]) + 1。因此只需要寻找满足长度最长的字典串恰好能和当前后缀完美匹配，我们可以选择只让后缀的子后缀匹配，所以是区间转移，用线段树辅助进行DP 转移。
复杂度O(300000 · (26 + log n))。

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
struct Info {
    int mx = inf;
};
Info operator+(const Info &a, const Info &b) {
    return {min(a.mx, b.mx)};
}
void solve() {
    cin >> n;
    AC ac;
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        string t;
        cin >> t;
        ac.add(t);
    }
    ac.work();
    s = " " + s;
    int len = s.size() - 1;
    vector<int> dp(len + 1, inf);
    SegmentTree<Info> seg(len + 1);
    int p = 1;
    dp[0] = 0;
    seg.modify(0, {dp[0]});
    deb(inf);
    for (int i = 1; i <= len; i++) {
        p = ac.next(p, s[i] - 'a');
        int tmp = ac.mxsuf(p);
        deb(tmp);
        if (tmp == 0)
            continue;
        int l = max(0, i - tmp);
        dp[i] = min(dp[i], seg.rangeQuery(l, i).mx + 1);
        seg.modify(i, {dp[i]});
    }
    if (dp[len] == inf)
        cout << -1 << endl;
    else
        cout << dp[len] << endl;
}

4.给出一个字典，至多包含60 个字典串，且字典串总长度不超过100。
求所有长度为M(≤ 100) 的串中（共26M26^M 个），有多少个串至少包含一
个字典串

Sol:考虑容斥，答案= 26M26^M- 完全不包含字典串的串个数。
包含与不包含本质上都是字符串匹配问题，因此本题为字符串多模式匹
配，很容易想到利用AC 自动机。
设$f[len][u] $表示长度为len 的字符串，当前匹配到了AC 自动机的u 节
点的方案数。
转移时枚举下一个字符，然后找到匹配的AC 自动机节点v(这一步的复
杂度为O(depth))，如果v 是一个终止节点，则是一个不合法的转移。

复杂度O(M · 100 · 100 · 26) =$ 2.7 · 10^7$

加强长度为M=10000

  • Trie 图
    用上题的做法复杂度高达$2.7 · 10^9 不能通过。因此需要进行优化：可以比较容易的观察到，可以预处理出不能通过。因此需要进行优化： 可以比较容易的观察到，可以预处理出trans[u][ch]$ =AC 自动机节点u，后
    面添加字符ch 后会转移到哪个节点。如此可以省掉跳Fail 链的复杂度。
    求$trans[u][ch] $时，讨论：
    • 如果u 节点有ch 后继边，则trans[u][ch]=nxt[u][ch]trans[u][ch] = nxt[u][ch]。
    • 否则，trans[u][ch]=trans[Fail[u]][ch]，trans[u][ch] = trans[Fail[u]][ch]。
      因此trans 数组也需要使用bfs 来求，可以和AC 自动机的构造放在一起进行

实现：由于为了卡做法，本题取模卡常，需要用取模类

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
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
 
template <class T> constexpr T power(T a, i64 n) {
    T res{1};
    for (; n > 0; n /= 2, a *= a) {
        if (n % 2 == 1) {
            res *= a;
        }
    }
    return res;
}
 
template <i64 P> constexpr i64 mul(i64 a, i64 b) {
    i64 res = a * b - i64(1.0L * a * b / P - 0.5L) * P;
    return res % P;
}
 
template <i64 P> struct ModInt {
    static i64 M;
    constexpr static void setMod(i64 m) { ModInt::M = m; }
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return M;
        }
    }
    i64 x;
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        } else if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr ModInt() : x{} {}
    constexpr ModInt(i64 x) : x{norm(x % getMod())} {}
    constexpr i64 val() const { return x; }
    explicit constexpr operator i64() const { return x; }
    constexpr ModInt operator-() const { return ModInt(getMod() - x); }
    constexpr ModInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr ModInt &operator+=(const ModInt &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt &rhs) {
        if (getMod() < (1LL << 31)) {
            x = 1LL * x * rhs.x % P;
        } else {
            x = mul<getMod()>(x, rhs.x);
        }
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt &rhs) { return *this *= rhs.inv(); }
    friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) { return lhs += rhs; }
    friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) { return lhs -= rhs; }
    friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) { return lhs *= rhs; }
    friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) { return lhs /= rhs; }
    friend constexpr bool operator<(const ModInt &lhs, const ModInt &rhs) { return lhs.val() < rhs.val(); }
    friend constexpr bool operator==(const ModInt &lhs, const ModInt &rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(const ModInt &lhs, const ModInt &rhs) { return lhs.val() != rhs.val(); }
    friend istream &operator>>(istream &is, ModInt &rhs) {
        i64 x;
        is >> x;
        rhs = x;
        return is;
    }
    friend ostream &operator<<(ostream &os, const ModInt &rhs) { return os << rhs.val(); }
};
 
template <> i64 ModInt<0>::M = 1000000007;
 
template <i64 V, i64 P> constexpr ModInt<P> CInv = ModInt<P>(V).inv();
 
constexpr int P = 10007;
using Z = ModInt<P>;

考虑对于一个字典串的终止节点，它的fail树子树都会被染成非法节点，所以dfs去完成染色是容易的。但为了减小常数，我们可以在ac自动机的构建过程去维护vis表示是不是包含

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int add(const string &a) {  // 向Trie树中添加字符串
       int p = 1;              // 从伪根节点开始
       for (auto c : a) {
           int x = c - 'A';
           if (t[p].next[x] == 0) {
               t[p].next[x] = newNode();  // 创建新节点，并更新next数组
               t[t[p].next[x]].len = t[p].len + 1;
           }
           p = t[p].next[x];  // 移动到下一个节点
       }
       t[p].vis = 1;
       t[p].mxsuf = a.size();
       return p;  // 返回最后一个字符对应的节点索引
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 void work() {  // 构建AC自动机的后缀链接
        queue<int> q;
        q.push(1);

        while (!q.empty()) {
            int x = q.front();
            q.pop();
            t[x].mxsuf = max(t[x].mxsuf, t[t[x].fail].mxsuf);
              t[x].vis |= t[t[x].fail].vis;
            for (int i = 0; i < asz; i++) {
                if (t[x].next[i] == 0) {                  // 如果当前节点没有对应字符的转移
                    t[x].next[i] = t[t[x].fail].next[i];  // 设置为后缀链接节点的对应转移
                } else {
                    t[t[x].next[i]].fail = t[t[x].fail].next[i];  // 设置新节点的后缀链接
//                     t[t[x].next[i]].vis |= t[t[t[x].fail].next[i]].vis;
                    // t[t[x].next[i]].ended |= t[t[t[x].link].next[i]].ended;
                    q.push(t[x].next[i]);
                }
            }
        }
    }

考虑每层的长度的转移是互相不牵连的，用滚动数组dp.本题在ac自动机上转移主要关注的是vis标记的躲避，与具体最长border无关。这里的ac自动机节点看作一个状态。

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
void solve() {
    AC ac;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ac.add(s);
    }
    ac.work();
    int tot = ac.size() - 1;
    vector<Z> dp(tot + 1);
    dp[1] = 1;
    for (int i = 1; i <= m; i++) {
        vector<Z> ndp(tot + 1);
        for (int p = 1; p <= tot; p++) {
            for (int x = 0; x < 26; x++) {
                int v = ac.next(p, x);
                if (ac.vis(v))
                    continue;
                ndp[v] += dp[p];
            }
        }
        dp = move(ndp);
        // dp = move(ndp); 的核心作用是通过移动语义避免拷贝，
        // 从而提高性能。ndp 在执行这句代码后可能会变为空或处于未定义状态，因此后续不要再直接使用 ndp。
    }
    Z ans = 0;

    for (int i = 1; i <= tot; i++) {
        ans += dp[i];
    }
     cout << power(Z(26), m) - ans << "\n";
}

6.给出N ≤ 2, 000 个01 串，它们每一个表示一段病毒序列，病毒代码总
长度不超过30, 000。
求是否存在无限长度的01 串，不包含任意病毒序列作为子串。

Sol:本题本质是问：Trie 图上（去掉所有终止节点）是否存在无限长度的路
径，充要条件为：有环。
因此本题需要先构造AC 自动机，然后补全成为Trie 图，找到所有包含病毒序列的节点。使用拓扑排序或者dfs判定是否有环。

  • 注意，这个环必须是root 节点可达的。
    复杂度O(30, 000 · 2)。
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
void solve() {
    int n;cin >> n;
    AC ac;
    for (int i = 1; i <= n; i++) {string s;cin >> s;ac.add(s);}
    ac.work();
    int tot = ac.size() - 1;
    vector<vector<int>> e(tot + 1);
    for (int i = 1; i <= tot; i++) {
        for (int j = 0; j < 2; j++) {
            int v = ac.next(i, j);
            if (ac.vis(i))continue;
            e[i].push_back(v);
        }
    }
    vector<int> st(tot + 1);
    auto dfs = [&](auto self, int u) {
        st[u] = 1;
        for (auto v : e[u]) {
            if (st[v] == 2)continue;
            if (st[v] == 1)return true;
            if (self(self, v))return true;
        }
        st[u] = 2;
        return false;
    };
    bool flag = dfs(dfs, 1);
    if (flag)cout << "TAK";
    else cout << "NIE";
}

8.CF547E给出N 个字符串，设f(S, T) 表示T 在S 中的出现次数。
给出Q 次询问：给定L, R, K，求∑i=Li≤Rf(Si,SK)\sum_{i=L}^{i\leq R} f(S_{i}, S_{K})

本题做法很多，其中一种做法是《AC 自动机Fail 树Dfs 序上建可持久
化线段树》。

  • 先建出AC 自动机，在回答询问的时候先找到SKS_{K}所在的节点u，那么
    完整包含字符串SKS_{K} 的状态节点一定位于u 的Fail 树子树内。
    即问题等价于询问u 的Fail 树子树内，SLS_{L}, SL+1S_{L+1}, · · · , SRS_{R} 的前缀节点个
    数有多少。
    考虑子树求和，比较容易转化为Dfs 序的区间求和，对字典串的区间询问，容易转化成持久化数据结构。即Dfs 序上建可持久化线段树。

具体来说对每个字符串都会在前缀结点上标记加1，我们去结点的dfs序对应位置上加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
AC ac;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> pos(n + 1);
    vector<string> s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        pos[i] = ac.add(s[i]);
    }
    ac.work();
    int tot = ac.size() - 1;
       
    vector<vector<int>> e(tot + 1);
    for (int i = 2; i <= tot; i++) {
        e[ac.fail(i)].push_back(i);
    }
    deb(e);
    vector<int> in(tot + 1), out(tot + 1);
    int idx = 0;
    auto dfs = [&](auto self, int u) -> void {
        deb(u);
        in[u] = ++idx;
        for (auto v : e[u]) {
            self(self, v);
        }
        out[u] = idx;
    };

    dfs(dfs, 1);
    Segment<Info> seg(tot + 5);
    vector<int> ver{0};
    for (int i = 1; i <= n; i++) {
        int prev = ver.back();
        for (int p = 1; auto c : s[i]) {
            p = ac.next(p, c);
            prev = seg.modify(prev, in[p], {1});  // 每次都有当前字符串长度的修改
            // 一个版本需要开len*log(len)的新点
        }
        ver.push_back(prev);  // 以一个字符串为一个版本
    }

    for (int i = 1; i <= m; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        Info res = seg.rangeQuery(ver[l-1], ver[r], in[pos[k]], out[pos[k]] + 1);
        cout << res.x << endl;
    }
}

考虑使用轻量级的dfs序配合树状数组。离线询问，将询问差分，只要求k在前缀L-1中出现次数和求k在前缀R中出现次数。

将询问挂在这两个位置，顺序扫描字符串。每次将当前字典串上的前缀节点加1，然后处理当前节点挂的多个询问，注意加个op表示是加还是减，对于查询就是对当前k的fail树子树内求和

code：

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
```

10.https://www.luogu.com.cn/problem/P2414[NOI2011] 阿狸的打字机

题意：给出一颗字典树，多次查询第x个字符串在第y个字符串出现了多少次？

Sol:首先题目以特定的当时生成字典树，仔细思考发现我们不能把所有构成的字符串存下来，也不能每次从头开始走路，而是要动态维护一个p指针和字典树节点的父亲来完成建树。

```c++
 struct Node {       // 表示Trie树的一个节点
        int len;        // 节点对应的字符串的长度
        int fail;       // 节点的后缀链接
        int mxsuf = 0;  // 后缀的恰好匹配一个完整的字典串
        bool vis = 0;   // 这个状态是不是存在子串是字典串
        array<int, asz> next;
        int fa = 1;//字典树的父亲
        // 表示从当前节点到下一个节点的转换，数组大小为字母表大小
        Node() : len{0}, fail{0}, next{} {}
    }; 

int add(int p, char c, char offset = 'a') {  // 向Trie树中添加字符串                                      
        int x = c - offset;
        if (t[p].next[x] == 0) {
            t[p].next[x] = newNode();  // 创建新节点，并更新next数组
            t[t[p].next[x]].len = t[p].len + 1;
            t[t[p].next[x]].fa = p;
        }
        p = t[p].next[x];  // 移动到下一个节点
        return p;  // 返回最后一个字符对应的节点索引
    }

考虑问题本身：x在y中出现了多少次，就是x的fail树子树内有多少个y的字典树前缀结点。我们需要子树求和，考虑dfs序加树状数组完成这个操作。

  • 把询问挂到y上，dfs字典树动态维护标记，进去的时候加1，出来的时候减1，这样能保证每次只查单串的贡献，每次退出递归的时候判一下这个点上有没有询问。

细节：要记录pos数组表示第x个字符串的结尾节点编号。字典树dfs由于建的是trie图所以我们需要判一下长度来完成正确的字典树遍历。

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
AC ac;
void solve() {
    string s;cin >> s;string tmp;
    vector<int> pos; pos.push_back(-1);
    int n = 0,p = 1;
    for (auto x : s) {
        if (x == 'B') {
            p = ac.fa(p);
        } else if (x == 'P') {
            n++;
            pos.push_back(p);
        } else
            p = ac.add(p, x);
    }

    //------------------------------------//
    ac.work();
    int tot = ac.size() - 1;
    vector<bool> vis(tot + 1);
    for (int i = 1; i <= n; i++) vis[pos[i]] = true;
    //-----------------------------------------
    int m;
    cin >> m;
    vector<vector<pii>> q(tot + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        q[pos[y]].push_back({pos[x], i});
    }
    vector<int> ans(m + 1);
    //-----------------------------------------------
    vector<vector<int>> e(tot + 1);
    for (int i = 2; i <= tot; i++) e[ac.fail(i)].push_back(i);
    vector<int> l(tot + 1), r(tot + 1);
    int idx = 0;
    auto dfs = [&](auto self, int u) -> void {
        l[u] = ++idx;
        for (auto v : e[u]) {
            self(self, v);
        }
        r[u] = idx;
    };
    dfs(dfs, 1);
    //-------------------------------------------------
    Fwk<int> fw(tot + 1);
    auto cal = [&](auto self, int u) -> void {
        fw.add(l[u], 1);
        for (int i = 0; i < 26; i++) {
            int v = ac.next(u, i);
            if (ac.len(v) == ac.len(u) + 1) {
                self(self, v);
            }
        }
        if (vis[u]) {
            for (auto [x, id] : q[u]) {
                ans[id] = fw.rangeSum(l[x] - 1, r[x]);
            }
        }
        fw.add(l[u], -1);
    };
    cal(cal, 1);
    for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}