NekoNowcoder

Appearance

字符串树 - 题解 ​

标签与难度 ​

标签: AC自动机, 最小生成树, 朱刘算法, Edmonds算法, 左偏树, 图论, 字符串 难度: 2600

题目大意喵~ ​

主人你好呀，这道题是关于字符串和树的有趣问题，喵~

题目给了我们 n 个字符串。我们需要构建一棵特殊的、带角色标签的有根树，叫做“子串表示树”。这棵树需要满足一个条件：对于输入的所有字符串的 每一个子串，树上都存在一条从祖先节点 u 到后代节点 v 的路径，这条路径上的边权（都是小写字母）依次拼接起来，正好等于这个子串。

在所有满足条件的“子串表示树”中，我们要找到节点数最少的那一棵，也就是“最小子串表示树”，然后输出它的节点个数。是不是听起来就很有挑战性呀？嘿嘿~

解题思路分析 ​

这道题的核心是“用最少的节点表示出所有的子串”，这听起来就像一个压缩和信息表示的问题，喵~。直接思考如何构建这棵树可能会有点绕，所以我们先换个角度，看看用什么工具能方便地处理“所有子串”这种信息。

Step 1: 字符串处理的利器 — AC自动机 ​

一看到“多个字符串”和“所有子串”，我的DNA就动了！这不就是 AC自动机 的主场嘛，的说！

AC自动机是在一堆模式串（这里就是我们输入的 n 个字符串）上构建的Trie树，并增加了“失配指针”（fail链）。它有两个非常棒的性质：

  1. Trie结构: 从根节点出发的任意一条路径都对应一个模式串的前缀。
  2. fail链: 如果在节点 u 匹配失败，可以跳到 fail[u] 继续，fail[u] 指向的节点代表的字符串是 u 代表字符串的最长后缀，且这个后缀也是所有模式串的前缀之一。

我们可以先将所有输入的 n 个字符串建成一个AC自动机。这个自动机的每个节点都唯一对应着一个前缀。设AC自动机共有 tot 个节点（从1到tot，1是根）。这些节点就是我们构建最终答案的“素材”，喵~

Step 2: 把问题转化为图论模型 ​

现在我们有了AC自动机的 tot 个节点。题目要求我们构建一棵树，用最少的节点表示所有子串。一个惊人的、但非常关键的结论是：所有子串都可以被AC自动机中的节点和它们之间的关系所表示。

我们可以把这个问题建模成一个 最小生成树 问题，但不是普通的MST，而是有向图的 最小生成树（最小树形图 / Minimum Spanning Arborescence）。

想象一下，我们最终要构建的“最小子串表示树”的节点，就是从AC自动机的 tot 个节点中选出来的一部分。为了让AC自动机的每个状态（代表一个前缀）都能被“表示”出来，它必须在我们的最终结构中有个“来源”或者说“父亲”。

对于AC自动机中任意一个非根节点 i，它有两个潜在的“父亲”来源：

  1. Trie树上的父亲 fa[i]: 节点 i 是由 fa[i] 通过一个字符转移过来的。这代表了一种自然的字符串延伸关系，str(i) = str(fa[i]) + c。我们可以认为，选择这条依赖关系，相当于我们“按部就班”地构建 str(i)，这需要付出代价。我们把这条有向边 fa[i] -> i 的权重设为 1，代表“创造”一个新节点的成本。
  2. fail指针指向的节点 fail[i]: fail[i] 代表的字符串是 str(i) 的一个后缀。这代表了一种结构上的复用关系。我们可以认为，str(i) 的信息可以由 str(fail[i]) 的信息“派生”出来，因为后缀是其一部分。这种“派生”是高效的，我们可以认为它不产生新的成本。所以，我们建立一条有向边 fail[i] -> i，权重设为 0。

现在，我们的问题就清晰多啦！我们有了一个包含 tot 个节点和许多带权有向边的图。我们需要为除了根节点1之外的每个节点 i，都选择一条唯一的入边（即选择一个父亲），使得：

  • 所有节点最终形成一棵以1为根的树（树形图）。
  • 所有选择的边的总权重之和最小。

这正是 最小树形图 的定义！

Step 3: 求解最小树形图 — 朱刘/Edmonds算法 ​

求解最小树形图的标准算法是 朱刘算法（Chu-Liu/Edmonds algorithm）。这个算法的流程比较复杂，通常用 左偏树 来优化，可以将复杂度降低到 O(Elog⁡V)O(E \log V)，其中 VV 是点数， EE 是边数。

算法的大致思路是：

  1. 对每个非根节点，选择一条权值最小的入边。
  2. 如果选出的边集合没有环，那么恭喜，它就是最小树形图！
  3. 如果出现了环，就将环缩成一个点，并更新指向环内节点的边的权值，然后在新图上继续递归求解。

在我们的题目中，V 就是AC自动机的节点数 tot，E 大约是 2 * tot。

Step 4: 解释最终答案 ​

朱刘算法会给我们一个最小的总权值 min_cost。这个 min_cost 是什么呢？ 根据我们之前的设定，权值为1的边是 fa[i] -> i，权值为0的边是 fail[i] -> i。所以，min_cost 正是我们在最优选择中，选择了 fa[i] -> i 这种“Trie父亲”边的数量。

每一个选择 fa[i] -> i 的决策，都对应着我们认为节点 i 是一个“基础”的、不可被其他节点“派生”的节点。这些“基础”节点，加上永恒的根节点1，就构成了我们“最小子串表示树”的骨架。

所以，最小子串表示树的节点数 = (选择Trie父亲边的数量) + (根节点) = min_cost + 1。

总结一下我们的完整流程：

  1. 将所有输入字符串构建成一个AC自动机。
  2. 根据AC自动机的Trie父子关系和fail关系，建立一个有向图。fa[i] -> i 边权为1，fail[i] -> i 边权为0。
  3. 以AC自动机的根节点为根，运行朱刘算法（用左偏树优化）求最小树形图的权值 min_cost。
  4. 最终答案就是 min_cost + 1。

好啦，思路清晰了，让我们一起把它实现出来吧，喵~！

代码实现 ​

这是我根据上面的思路，精心重构的代码哦~ 注释超详细的，希望能帮到你！

cpp
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

// 使用命名空间让代码结构更清晰喵~
namespace ACA {
    const int MAX_NODES = 1000005;
    const int ALPHABET_SIZE = 26;

    int trie[MAX_NODES][ALPHABET_SIZE];
    int fail_link[MAX_NODES];
    int trie_parent[MAX_NODES];
    int node_count = 1;

    // 插入一个字符串到Trie树中
    void insert(const std::string& s) {
        int current_node = 1;
        for (char ch : s) {
            int c = ch - 'a';
            if (!trie[current_node][c]) {
                trie[current_node][c] = ++node_count;
                trie_parent[node_count] = current_node;
            }
            current_node = trie[current_node][c];
        }
    }

    // 构建Fail指针，把Trie变成AC自动机
    void build() {
        std::queue<int> q;
        // 处理根节点的子节点
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            if (trie[1][i]) {
                fail_link[trie[1][i]] = 1;
                q.push(trie[1][i]);
            } else {
                trie[1][i] = 1; // 优化：不存在的路径直接指向根
            }
        }

        // BFS构建fail指针
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < ALPHABET_SIZE; ++i) {
                int v = trie[u][i];
                if (v) {
                    fail_link[v] = trie[fail_link[u]][i];
                    q.push(v);
                } else {
                    trie[u][i] = trie[fail_link[u]][i];
                }
            }
        }
    }
}

// 朱刘算法（Edmonds' Algorithm）用左偏树优化
namespace Edmonds {
    const int MAX_TOTAL_NODES = 2000010; // 节点数 + 缩点产生的点数
    const int MAX_EDGES = 3000010;

    struct Edge {
        int from, to;
        int weight;
    };

    // 左偏树节点
    struct LeftistNode {
        int l_child = 0, r_child = 0;
        int dist = 0;
        int tag = 0; // 懒标记，用于区间加
        Edge edge;
    };

    LeftistNode heap[MAX_EDGES];
    int heap_count = 0;
    
    int root[MAX_TOTAL_NODES]; // 每个节点对应一个左偏树的根
    int disjoint_set[MAX_TOTAL_NODES];
    bool visited[MAX_TOTAL_NODES];
    int path_stack[MAX_TOTAL_NODES];

    int find_set(int x) {
        return x == disjoint_set[x] ? x : disjoint_set[x] = find_set(disjoint_set[x]);
    }

    // 创建一个新的左偏树节点
    int new_node(const Edge& e) {
        heap[++heap_count].edge = e;
        heap[heap_count].l_child = heap[heap_count].r_child = 0;
        heap[heap_count].dist = heap[heap_count].tag = 0;
        return heap_count;
    }
    
    void push_down(int x) {
        if (heap[x].tag) {
            int lc = heap[x].l_child, rc = heap[x].r_child;
            if (lc) {
                heap[lc].edge.weight += heap[x].tag;
                heap[lc].tag += heap[x].tag;
            }
            if (rc) {
                heap[rc].edge.weight += heap[x].tag;
                heap[rc].tag += heap[x].tag;
            }
            heap[x].tag = 0;
        }
    }

    // 合并两个左偏树
    int merge(int x, int y) {
        if (!x || !y) return x + y;
        push_down(x);
        push_down(y);
        if (heap[x].edge.weight > heap[y].edge.weight) std::swap(x, y);
        
        heap[x].r_child = merge(heap[x].r_child, y);
        
        if (heap[heap[x].l_child].dist < heap[heap[x].r_child].dist) {
            std::swap(heap[x].l_child, heap[x].r_child);
        }
        heap[x].dist = heap[heap[x].r_child].dist + 1;
        return x;
    }

    // 弹出堆顶（最小元素）
    int pop(int x) {
        push_down(x);
        return merge(heap[x].l_child, heap[x].r_child);
    }
    
    void add_edge(const Edge& e) {
        root[e.to] = merge(root[e.to], new_node(e));
    }

    // 主算法
    long long solve(int n, int r) {
        for (int i = 1; i <= 2 * n; ++i) disjoint_set[i] = i;

        long long total_weight = 0;
        int contracted_node_count = n;
        int top = 0;
        path_stack[++top] = r;
        visited[r] = true;

        while (root[path_stack[top]]) {
            int u = path_stack[top];
            
            // 找到u的当前最小入边
            int min_edge_node = root[u];
            Edge current_edge = heap[min_edge_node].edge;

            int from_root = find_set(current_edge.from);
            
            // 如果边的起点和终点在同一个集合（自环），则该边无效
            if (from_root == u) {
                root[u] = pop(root[u]);
                continue;
            }
            
            // 如果起点尚未访问，则加入路径栈
            if (!visited[from_root]) {
                path_stack[++top] = from_root;
                visited[from_root] = true;
                continue;
            }
            
            // 发现环！开始缩点
            int new_contracted_node = ++contracted_node_count;
            while (visited[from_root]) {
                int v = path_stack[top--];
                visited[v] = false;
                disjoint_set[v] = new_contracted_node;

                int edge_v_node = root[v];
                int weight = heap[edge_v_node].edge.weight;

                // 环内边的权值加到总和里
                total_weight += weight;
                
                // 更新指向环外节点的边的权值
                heap[edge_v_node].tag -= weight;
                
                // 将环上节点的堆合并到新点上
                root[v] = pop(root[v]);
                root[new_contracted_node] = merge(root[new_contracted_node], root[v]);
            }
            
            path_stack[++top] = new_contracted_node;
            visited[new_contracted_node] = true;
        }
        
        // 加上路径栈上各节点选择的最小入边权值
        while(top > 1) {
            int u = path_stack[top--];
            total_weight += heap[root[u]].edge.weight;
        }

        return total_weight;
    }
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        ACA::insert(s);
    }

    ACA::build();

    // 构建朱刘算法的图
    for (int i = 2; i <= ACA::node_count; ++i) {
        // Trie父子边，权为1
        Edmonds::add_edge({ACA::trie_parent[i], i, 1});
        // Fail边，权为0
        Edmonds::add_edge({ACA::fail_link[i], i, 0});
    }

    long long min_cost = Edmonds::solve(ACA::node_count, 1);

    // 最终节点数 = 最小代价 + 根节点
    std::cout << min_cost + 1 << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(∑∣si∣+Vlog⁡E)O(\sum |s_i| + V \log E)，其中 ∑∣si∣\sum |s_i| 是总串长，用于构建AC自动机。VV 是AC自动机的节点数， EE 是为朱刘算法构建的边数。在这里 V≈∑∣si∣V \approx \sum |s_i|，E≈2VE \approx 2V。朱刘算法使用左偏树优化的复杂度是 O(Elog⁡V)O(E \log V)。所以总复杂度约为 O(∑∣si∣log⁡(∑∣si∣))O(\sum |s_i| \log (\sum |s_i|))。

  • 空间复杂度: O(∑∣si∣)O(\sum |s_i|)。AC自动机和朱刘算法都需要与总串长成正比的空间来存储节点、边和左偏树等数据结构。

知识点总结 ​

这真是一道融合了多种算法的超酷题目呀，喵！解决它需要掌握以下知识点：

  1. AC自动机: 解决多模式串匹配问题的神器。理解它的Trie结构和fail指针是解题的第一步。
  2. 图论建模: 能够把看似与图无关的问题，通过分析其内在的依赖关系和成本，转化为图论模型。这是算法竞赛中非常重要的抽象能力。
  3. 最小树形图 (Minimum Spanning Arborescence): 了解有向图的最小生成树概念，知道它的目标是在有向图中为每个非根节点找一个唯一的父亲，形成一棵树，并使总权值最小。
  4. 朱刘/Edmonds算法: 解决最小树形图问题的经典算法，特别是其核心思想——“找环、缩点、更新权值”。
  5. 左偏树: 一种可并堆，是优化朱刘算法的常用数据结构，能高效地维护每个节点的最小入边集合，并支持合并操作。

通过这道题，我们不仅练习了字符串算法，还深入到了高级图论算法，真是收获满满呢，主人！以后遇到类似“最小依赖”或“最小成本覆盖”的问题，都可以想想是否能往最小树形图的方向建模哦~ 喵~