思路与算法

Trie节点代表残余后缀语言。插入建立路径并标终止；纠缠操作把两个前缀节点放入并查集合并队列，合并终止标志，同字符后继冲突继续入队。查询沿代表元的转移行走，只读不补路径。

正确性说明

纠缠要求两个前缀后可接的所有后缀完全相同，因此必须合并终止性与各字符后继语言。队列闭包恰好反复执行这些必要等式；没有额外合并不受等式约束的节点，得到最小闭包。并查集中的环能表示无限多个字符串，不需要逐个生成。

复杂度

设最多建立V个节点，读入字符总数S。初始化及实际合并处理10个转移，配合按大小合并与路径压缩，总O((10V+S)α(V))时间，O(10V)空间。

易错点

纠缠前缀不存在时可以建立路径，查询不存在时不能建立。合并会产生自环，不能依赖Trie仍为树。终止标志须取或。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Trie {
    vector<array<int, 10>> go;
    vector<int> p, sz, terminal;
    Trie() {
        node();
    }
    int node() {
        int u = p.size();
        array<int, 10> a;
        a.fill(-1);
        go.push_back(a);
        p.push_back(u);
        sz.push_back(1);
        terminal.push_back(0);
        return u;
    }
    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    int walk(const string &s, bool create) {
        int u = 0;
        for (char c : s) {
            u = find(u);
            int z = c - '0';
            if (go[u][z] < 0) {
                if (!create)
                    return -1;
                int v = node();
                go[u][z] = v;
            }
            u = go[u][z];
        }
        return find(u);
    }
    void merge(int a, int b) {
        vector<pair<int, int>> q(1, {a, b});
        for (size_t at = 0; at < q.size(); at++) {
            int x = find(q[at].first), y = find(q[at].second);
            if (x == y)
                continue;
            if (sz[x] < sz[y])
                swap(x, y);
            p[y] = x;
            sz[x] += sz[y];
            terminal[x] |= terminal[y];
            for (int c = 0; c < 10; c++)
                if (go[y][c] >= 0) {
                    if (go[x][c] < 0)
                        go[x][c] = go[y][c];
                    else
                        q.push_back({go[x][c], go[y][c]});
                }
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin >> m;
    Trie t;
    while (m--) {
        int k;
        string s, a;
        cin >> k >> s;
        if (k == 1)
            t.terminal[t.walk(s, true)] = 1;
        else if (k == 2) {
            int u = t.walk(s, false);
            cout << (u >= 0 && t.terminal[u]) << '\n';
        } else {
            cin >> a;
            int u = t.walk(s, true), v = t.walk(a, true);
            t.merge(u, v);
        }
    }
}