HardStringProblem - 题解

标签与难度

标签: 字符串, 后缀自动机, 广义后缀自动机, KMP算法, 最小表示法, 周期串 难度: 2500

题目大意喵~

你好呀，未来的算法大师！本喵今天带来了一道关于无限魔咒的有趣问题，喵~

题目是这样的：我们有 n 个咒语，每个咒语都是由一个给定的字符串（我们叫它“循环节”）无限重复形成的。比如说，循环节是 'abc'，那么形成的无限咒语就是 'abcabcabc...'。

我们的任务是，找出所有这 n 个无限咒语共同拥有的子串有多少个。子串是不能重复计算的哦！举个例子，如果 'a' 和 'b' 都是公共子串，那么就算作两个。

输入: 第一行是一个整数 n，表示咒语的数量。 接下来 n 行，每行一个字符串，代表一个咒语的循环节。

输出: 一个整数，表示不同公共子串的总数。

解题思路分析

这道题看起来和无限长的字符串有关，是不是有点吓人呀？别怕别怕，本喵会一步步带你解开它的神秘面纱，就像解开一个毛线球一样简单，喵~

第一步：给无限咒语一个“身份证”

一个无限咒语是由它的循环节决定的。但是，不同的循环节可能会产生完全相同的无限咒语哦！比如说，'ab' 和 'abab' 产生的都是 'ababab...'。还有，'abc' 和 'bca' 产生的无限咒语 'abcabc...' 和 'bcabca...'，它们包含的子串集合也是一模一样的。

为了方便比较，我们需要给每个无限咒语一个独一无二的“身份证”，也就是最小循环表示。

1. 找到最小循环节: 对于一个字符串 s，比如 'ababab'，它的最小循环节是 'ab'。我们可以用 KMP 算法的 pi 数组（也叫 next 数组）来找到它。一个长度为 L 的字符串 s，它的最短周期长度是 p = L - pi[L-1]。如果 L 能被 p 整除，那么最小循环节就是 s 的前 p 个字符。否则，最小循环节就是 s 本身。

2. 找到字典序最小的循环移位: 找到了最小循环节，比如 'bca'，它和 'cab', 'abc' 产生的子串集合是一样的。为了统一，我们取所有循环移位中字典序最小的那个作为代表。比如对于 'bca'，它的循环移位有 'bca', 'cab', 'abc'，其中 'abc' 是最小的。我们就用 'abc' 作为这个无限咒语的“身份证”。这个过程叫做最小表示法。

经过这两步，每个输入的字符串都被我们转化成了一个唯一的、标准的“身份证”啦！

第二步：一个特殊的陷阱

如果在转化之后，我们发现所有 n 个咒语的“身份证”都一模一样，这意味着什么呢？这意味着所有的无限咒语都是同一个！那么它们的公共子串就是这个无限咒语自己的所有子串。一个无限长的字符串，子串当然有无限多个啦！这种情况下，题目要求我们输出 -1。所以，如果所有“身份证”都相同，就直接输出 -1，然后开心地结束程序，喵~

第三步：公共子串的最大长度？

现在我们有了一堆不同的“身份证”（也就是唯一的最小循环节），比如 {C_1, C_2, ..., C_k}。我们要找的，就是同时是 (C_1)..., (C_2)..., ..., (C_k)... 这些无限咒语的子串的字符串。

这里有一个非常重要的突破口，让本喵用敏锐的猫眼告诉你！一个公共子串 t 不可能无限长。它的长度是有限的。那它的长度上限是多少呢？

假设 C_min 是所有“身份证”里最短的那个，长度是 L_min。如果一个公共子串 t 的长度大于等于 2 * L_min，会发生什么？

• 因为 t 是 (C_min)... 的子串，并且长度这么长，所以 t 内部必然完整地包含了 C_min 这个子串。
• 又因为 t 也是其他无限咒语 (C_j)... 的子串，所以 C_min 也必须是 (C_j)... 的子串。
• 一个最小循环节 C_min 要成为另一个无限咒语 (C_j)... 的子串，只有一种可能：C_min 是 C_j 的一个循环移位。
• 但我们已经把所有字符串都变成了它们各自的最小循环表示了！如果 C_min 是 C_j 的循环移位，那么它们的最小表示应该是相同的，也就是 C_min 应该等于 C_j。
• 这和我们正在处理一堆不同的“身份证”的前提矛盾了！

所以，结论就是：任何公共子串的长度，都必须小于 2 * L_min。

这个结论太棒了！它把一个无限的问题，变成了一个有限的问题。我们不再需要处理无限长的字符串了！

第四步：广义后缀自动机 (GSAM) 登场！

既然问题变成了在多个字符串中寻找公共子串，那么就是广义后缀自动机（GSAM）大显身手的时候啦！

1. 准备材料: 根据上面的结论，我们只需要考虑每个无限咒语 (C_j)... 的一个足够长的前缀，确保它包含了所有长度小于 2 * L_min 的子串。 一个安全的做法是，把每个 C_j 重复几遍。比如，把 C_j 变成 C_j + C_j + C_j。因为 L_min <= |C_j|，所以 2 * L_min <= 2 * |C_j|。而 C_j 重复三次得到的字符串，长度为 3 * |C_j|，它肯定包含了 (C_j)... 中所有长度不超过 2 * |C_j| 的子串。这就足够了！我们把这些新的、加长版的字符串记作 {S_1, S_2, ..., S_k}。

2. 建造GSAM: 我们把所有这些 S_j 都插入到一个广义后缀自动机里。

3. 计数: GSAM 的每个状态（除了初始状态）都代表了一个或多个子串。一个状态 u 代表的子串数量是 st[u].len - st[st[u].link].len。 我们想知道哪些子串是所有 S_j 共有的。所以，我们需要对每个状态 u，计算它代表的子串出现在了多少个不同的 S_j 中。

   • 我们可以用一个 count 数组，count[u] 记录状态 u 被多少个源字符串“拥有”。
   • 对于每个 S_j，我们遍历它，在 GSAM 上走。每走到一个状态 p，就说明 p 和它在 link 树上的所有祖先，都代表了 S_j 的子串。我们给这些状态的 count 值加一（当然，对于同一个 S_j，每个状态只加一次）。
   • 为了高效实现，我们可以用一个 visited 数组，每次处理一个新的 S_j 时，用一个独有的标记（比如 S_j 的编号 j）来记录访问过的状态。

4. 统计答案: 最后，我们遍历 GSAM 的所有状态 u。如果 count[u] 等于我们拥有的不同“身份证”的数量 k，那就说明这个状态代表的子串是所有咒语共有的！我们就把 st[u].len - st[st[u].link].len 加入总答案。

这样，我们就漂亮地解决了这个问题啦！是不是很有趣，喵~

代码实现

这是本喵根据上面的思路，为你精心准备的一份代码，注释超详细的哦！

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>

// KMP 算法的辅助函数，计算 pi 数组 (前缀函数)
// pi[i] 表示 s[0...i] 的最长相等前后缀的长度
std::vector<int> calculate_pi(const std::string& s) {
    int n = s.length();
    std::vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

// 获取字符串的规范表示形式 (最小循环节的最小字典序循环移位)
std::string get_canonical(const std::string& s) {
    if (s.empty()) {
        return "";
    }

    // 1. 找到最小循环节
    int n = s.length();
    auto pi = calculate_pi(s);
    int period_len = n - pi[n - 1];
    std::string minimal_period = s;
    if (n % period_len == 0) {
        minimal_period = s.substr(0, period_len);
    }

    // 2. 找到最小循环节的字典序最小循环移位 (最小表示法)
    // 使用 Booth's 算法的思想 (双指针法)
    int p_len = minimal_period.length();
    minimal_period += minimal_period; // 方便取循环子串
    int i = 0, j = 1, k = 0;
    while (i < p_len && j < p_len && k < p_len) {
        char char_i = minimal_period[i + k];
        char char_j = minimal_period[j + k];
        if (char_i == char_j) {
            k++;
        } else {
            if (char_i > char_j) {
                i = i + k + 1;
            } else {
                j = j + k + 1;
            }
            if (i == j) j++;
            k = 0;
        }
    }
    int min_idx = std::min(i, j);
    return minimal_period.substr(min_idx, p_len);
}

const int ALPHABET_SIZE = 26;

// 后缀自动机 (SAM) 的状态节点
struct SAM_State {
    int len, link;
    int next[ALPHABET_SIZE];

    SAM_State() : len(0), link(-1) {
        std::fill(next, next + ALPHABET_SIZE, 0);
    }
};

// 广义后缀自动机 (GSAM)
struct SuffixAutomaton {
    std::vector<SAM_State> st;
    int last;
    int node_count;

    SuffixAutomaton(int max_nodes) {
        st.resize(max_nodes);
        // 初始状态 0
        st[0].len = 0;
        st[0].link = -1;
        node_count = 1;
        last = 0;
    }

    void extend(char c_char) {
        int c = c_char - 'a';
        int cur = node_count++;
        st[cur].len = st[last].len + 1;
        
        int p = last;
        while (p != -1 && st[p].next[c] == 0) {
            st[p].next[c] = cur;
            p = st[p].link;
        }

        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[q].len == st[p].len + 1) {
                st[cur].link = q;
            } else {
                int clone = node_count++;
                st[clone].len = st[p].len + 1;
                std::copy(st[q].next, st[q].next + ALPHABET_SIZE, st[clone].next);
                st[clone].link = st[q].link;
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = clone;
                st[cur].link = clone;
            }
        }
        last = cur;
    }
    
    // 插入一个完整的字符串，每次插入前重置 last
    void insert_string(const std::string& s) {
        last = 0; 
        for (char ch : s) {
            extend(ch);
        }
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<std::string> canonical_forms;
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        canonical_forms.push_back(get_canonical(s));
    }

    // 排序并去重，得到唯一的规范表示
    std::sort(canonical_forms.begin(), canonical_forms.end());
    canonical_forms.erase(std::unique(canonical_forms.begin(), canonical_forms.end()), canonical_forms.end());

    if (canonical_forms.size() <= 1) {
        std::cout << -1 << std::endl;
        return 0;
    }

    // 准备插入到GSAM的字符串 (重复3次保证覆盖所有可能的公共子串)
    std::vector<std::string> strings_for_sam;
    size_t total_len = 0;
    for (const auto& s : canonical_forms) {
        strings_for_sam.push_back(s + s + s);
        total_len += strings_for_sam.back().length();
    }
    
    // 初始化SAM，大小为总长度的两倍是安全的
    SuffixAutomaton sam(total_len * 2 + 5);
    for (const auto& s : strings_for_sam) {
        sam.insert_string(s);
    }

    // 统计每个状态被多少个源字符串包含
    std::vector<int> state_counts(sam.node_count, 0);
    std::vector<int> visited_by_string_id(sam.node_count, 0);

    int k = canonical_forms.size();
    for (int i = 0; i < k; ++i) {
        int current_node = 0;
        for (char ch : strings_for_sam[i]) {
            int c = ch - 'a';
            current_node = sam.st[current_node].next[c];
            
            // 沿着 parent link 向上标记
            int p = current_node;
            while (p != -1 && visited_by_string_id[p] != i + 1) {
                visited_by_string_id[p] = i + 1;
                state_counts[p]++;
                p = sam.st[p].link;
            }
        }
    }

    // 计算最终答案
    long long ans = 0;
    for (int i = 1; i < sam.node_count; ++i) {
        if (state_counts[i] == k) {
            ans += sam.st[i].len - sam.st[sam.st[i].link].len;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O(\sum |s_i|)$

  • 预处理: 对每个输入字符串 s，计算它的规范形式需要 $O(|s|)$ 的时间（KMP 和最小表示法都是线性的）。所有字符串总共是 $O(\sum |s_i|)$。
  • 排序去重: 如果有 k 个唯一的规范形式，总长度为 N，排序需要 $O(N \log k)$。
  • GSAM 构建: 我们将每个规范形式重复三次，总长度仍然是 $O(\sum |s_i|)$ 级别。构建 GSAM 的时间是线性的，即 $O(\sum |S_j|)$。
  • 计数: 对每个加长后的字符串 S_j，我们在 GSAM 上遍历并向上爬 link 链。虽然看起来有嵌套循环，但可以证明，对单个字符串 S_j，总的标记操作次数是 $O(|S_j|)$ 的。所以总计数时间是 $O(\sum |S_j|)$。
  • 综上，总时间复杂度由字符串处理和 SAM 操作主导，近似为 $O(\sum |s_i|)$。

• 空间复杂度: $O(\sum |s_i|)$

  • 存储规范形式的字符串需要 $O(\sum |s_i|)$ 的空间。
  • GSAM 的状态数和转移数最多是总输入长度的常数倍（通常是2倍左右），所以空间是 $O(\sum |S_j|)$。
  • state_counts 和 visited_by_string_id 数组的大小也和 GSAM 的状态数成正比。
  • 因此，总空间复杂度是 $O(\sum |s_i|)$。

知识点总结

这道题是字符串算法的盛宴呀，喵~

1. 周期串理论: 理解字符串的周期和循环节是第一步，KMP 算法的 pi 数组是求最小周期的利器。
2. 最小表示法: 当处理循环同构的字符串时，这是一个非常重要的标准化工具，能有效避免重复和遗漏。
3. 广义后缀自动机 (GSAM): 解决多个字符串相关问题的神器！特别适合处理“公共子串”、“第k大子串”等问题。
4. 问题转化: 最关键的思维飞跃在于，通过分析公共子串的长度上限，将一个关于“无限”的问题转化为了一个在有限长度字符串上操作的“有限”问题。这在算法竞赛中是常见的化繁为简的技巧哦！

希望这篇题解能帮到你！继续加油，你一定能成为算法大师的，喵~ >w<