I. Fake News (hard) - 题解

比赛与标签

比赛: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated) 标签: string suffix structures 难度: *2300

题目大意喵~

主人，这道题是想让我们计算一个字符串 s 的“自相似性”呢！这个“自相似性”被定义成一个公式：

\sum_{p} (\text{count}(p))^2

这里的 p 是字符串 s 的所有 非空子串，而 count(p) 是子串 p 在 s 中作为子串出现的次数。

举个例子来理解一下，喵~ 如果 s = "aa"：

它有哪些不同的非空子串呢？有 "a" 和 "aa"。
"a" 出现了 2 次，所以 count("a") = 2。
"aa" 出现了 1 次，所以 count("aa") = 1。
那么总的“自相似性”就是 (count("a"))^2 + (count("aa"))^2 = 2^2 + 1^2 = 4 + 1 = 5 啦！

我们的任务就是，对于给定的字符串 s，算出这个值。

解题思路的奇妙旅程

一看到这个平方和的公式 ∑(count(p))^2，直接去枚举所有子串 p 再统计个数，肯定会超时的说！所以我们需要一种更优雅、更喵喵的方式来解决它！

第一步：魔法公式大变身！

让我们来对这个公式做一点小小的变形戏法，喵~ 对于任何一个子串 p，它的出现次数 k = count(p)，k^2 可以写成 k + k(k-1)。 k(k-1) 是什么呢？它等于 2 * (k * (k-1) / 2)，也就是 2 * C(k, 2)，即从 k 个相同的物品中选出 2 个的组合数！

所以，我们的总公式可以变成：

\sum_{p} (\text{count}(p))^2 = \sum_{p} \text{count}(p) + \sum_{p} \text{count}(p)(\text{count}(p)-1)

= \sum_{p} \text{count}(p) + 2 \times \sum_{p} C(\text{count}(p), 2)

现在问题被分成了两个部分：

第一部分 ∑ count(p)：这个式子代表“所有不同子串的出现次数之和”。这其实等价于字符串 s 中 所有子串（包括重复的）的总个数！对于一个长度为 n 的字符串，它的子串总数是 n * (n + 1) / 2。这部分很容易计算，耶！
第二部分 ∑ C(count(p), 2)：C(count(p), 2) 的意思是，对于一个出现了 count(p) 次的子串 p，我们从中任意选取两个，形成的 无序对 的数量。那么对所有 p 求和，就是计算字符串 s 中 所有完全相同的子串对 的总数量。

我们的核心任务，就是计算这个“相同子串对”的总数！

第二步：后缀数组 (SA) 和 LCP 数组闪亮登场！

怎么计算相同子串对的数量呢？这就要请出我们的字符串神器——后缀数组和LCP数组啦！

相同子串与公共前缀：两个子串相同，比如 s[i...i+L-1] 和 s[j...j+L-1]，等价于说，从 i 开始的后缀和从 j 开始的后缀，它们拥有一个长度至少为 L 的公共前缀。
LCP 的力量：一对后缀 suffix(i) 和 suffix(j) 拥有 LCP(suffix(i), suffix(j)) 个不同的公共前缀。每一个公共前缀就对应一个相同子串对。所以，相同子串对的总数就等于 所有后缀对的最长公共前缀（LCP）长度之和！

\text{相同子串对总数} = \sum_{0 \le i < j < n} \text{LCP}(\text{suffix}(i), \text{suffix}(j))

直接计算这个 O(n^2) 的和还是太慢了。但是，借助后缀数组（SA）和LCP数组，我们可以加速这个过程！

后缀数组 (SA): sa[i] 表示将所有后缀按字典序排序后，排在第 i 位的后缀的起始位置。
LCP 数组: lcp[i] 表示 sa[i] 和 sa[i+1] 这两个在排序后相邻的后缀的最长公共前缀长度。
关键性质: 任意两个后缀 sa[i] 和 sa[j] (假设 i < j) 的 LCP，等于它们之间所有相邻 LCP 的最小值，即 LCP(sa[i], sa[j]) = min(lcp[k]) for k from i to j-1。

所以，我们的任务又转化了：

\text{相同子串对总数} = \sum_{0 \le i < j < n} \min_{k=i}^{j-1} \text{lcp}[k]

这相当于计算 LCP数组的所有子数组的最小值之和！

第三步：单调栈的终极一击！

“计算一个数组所有子数组的最小值之和”，这是一个经典问题，可以用 单调栈 在 O(n) 时间内解决，喵！

具体做法是：我们遍历 LCP 数组中的每一个元素 lcp[i]，然后计算它作为 最小值 贡献了多少次。为了做到这一点，我们需要对每个 lcp[i] 找到：

left[i]: i 左边第一个比 lcp[i] 小的元素的位置。
right[i]: i 右边第一个比 lcp[i] 小或等于 的元素的位置。（使用 < 和 <= 来处理重复值，避免重复计算）

这样，lcp[i] 就是区间 (left[i], right[i]) 内的唯一最小值。以 lcp[i] 为最小值的子数组，其左端点可以在 (left[i], i] 中选择，有 i - left[i] 种选法；右端点可以在 [i, right[i]) 中选择，有 right[i] - i 种选法。所以，lcp[i] 的总贡献就是 lcp[i] * (i - left[i]) * (right[i] - i)。

我们把所有 lcp[i] 的贡献加起来，就得到了 S = ∑ C(count(p), 2)。

总结一下我们的计划：

计算 ans = n * (n + 1) / 2。
构建字符串 s 的后缀数组 sa 和 LCP 数组 lcp。
使用单调栈计算 S = ∑ lcp[i] * (i - left[i]) * (right[i] - i)。
最终答案就是 ans + 2 * S！完美，喵~

代码实现喵~

下面就是把我们的思路变成代码啦！本猫娘已经为主人准备好了带有详细注释的AC代码哦。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

// 构建后缀数组 SA (O(n log n))
// 使用倍增算法，将后缀的比较从单个字符扩展到 2, 4, 8... 长度的块
vector<int> buildSA(string s) {
    int n = s.size();
    vector<int> sa(n), rank(n), tmp(n);
    // 初始时，按单个字符排序
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    // 倍增过程，k 是当前比较的块的长度
    for (int k = 1; k < n; k *= 2) {
        // 自定义比较函数，比较两个后缀
        // 先比较前半部分 rank[i] 和 rank[j]
        // 如果相同，再比较后半部分 rank[i+k] 和 rank[j+k]
        auto cmp = [&](int i, int j) {
            if (rank[i] != rank[j])
                return rank[i] < rank[j];
            int ri = (i + k < n) ? rank[i + k] : -1; // 处理越界
            int rj = (j + k < n) ? rank[j + k] : -1;
            return ri < rj;
        };
        sort(sa.begin(), sa.end(), cmp);
        // 根据排序结果，重新计算 rank
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i-1]];
            if (cmp(sa[i-1], sa[i])) {
                tmp[sa[i]]++;
            }
        }
        rank = tmp;
    }
    return sa;
}

// 构建 LCP 数组 (O(n))
// 使用 Kasai's Algorithm
vector<int> buildLCP(string s, vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n);
    for (int i = 0; i < n; i++) {
        rank[sa[i]] = i; // rank[i] 是后缀 i 在 sa 中的排名
    }
    vector<int> lcp(n-1);
    int h = 0; // h 表示上一个后缀与其在 sa 中后继的 lcp 值
    for (int i = 0; i < n; i++) {
        if (rank[i] == n-1) { // 最后一个后缀没有后继
            h = 0;
            continue;
        }
        // 根据 LCP-Lemma, h' >= h - 1
        // j 是后缀 i 在 sa 中的后继
        int j = sa[rank[i] + 1];
        while (i+h < n && j+h < n && s[i+h] == s[j+h]) {
            h++;
        }
        lcp[rank[i]] = h;
        if (h > 0) h--; // 下一次计算从 h-1 开始
    }
    return lcp;
}

long long solve(string s) {
    int n = s.size();
    if (n == 0) {
        return 0;
    }
    vector<int> sa = buildSA(s);
    vector<int> lcp = buildLCP(s, sa);

    // 第一部分：所有子串的总数
    long long ans = (long long) n * (n+1) / 2;

    int m = n - 1; // lcp 数组的长度
    if (m <= 0) {
        return ans;
    }
    vector<long long> A(m);
    for (int i = 0; i < m; i++) {
        A[i] = lcp[i];
    }

    // 第二部分：计算 ∑ C(count(p), 2)
    // 使用单调栈计算 lcp 数组所有子数组的最小值之和

    // 计算每个元素左边第一个更小的元素的位置
    vector<int> left(m, -1);
    stack<int> st;
    for (int i = 0; i < m; i++) {
        while (!st.empty() && A[st.top()] >= A[i]) {
            st.pop();
        }
        if (!st.empty()) {
            left[i] = st.top();
        } else {
            left[i] = -1; // 左边没有更小的
        }
        st.push(i);
    }

    while (!st.empty()) st.pop(); // 清空栈

    // 计算每个元素右边第一个更小或相等的元素的位置
    // 注意这里 A[st.top()] > A[i] 是为了正确处理 lcp 值相等的情况
    vector<int> right(m, m);
    for (int i = m-1; i >= 0; i--) {
        while (!st.empty() && A[st.top()] > A[i]) {
            st.pop();
        }
        if (!st.empty()) {
            right[i] = st.top();
        } else {
            right[i] = m; // 右边没有更小或相等的
        }
        st.push(i);
    }

    // 计算所有相同子串对的总数 S
    long long S = 0;
    for (int i = 0; i < m; i++) {
        long long left_count = i - left[i];
        long long right_count = right[i] - i;
        S += A[i] * left_count * right_count;
    }

    // 最终答案 = 部分1 + 2 * 部分2
    ans += 2 * S;
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        cout << solve(s) << '\n';
    }
    return 0;
}

复杂度分析，喵~

时间复杂度: O(N log N) 的说。
- buildSA 函数使用倍增法，复杂度是 O(N log N)。
- buildLCP 函数使用 Kasai's 算法，复杂度是 O(N)。
- 单调栈部分计算 left 和 right 数组，每个元素入栈出栈一次，复杂度是 O(N)。
- 所以瓶颈在于后缀数组的构建，总时间复杂度为 O(N log N) 呐。
空间复杂度: O(N) 的说。
- sa, rank, lcp, left, right 等数组都需要 O(N) 的空间。

知识点与总结

这道题真是一场精彩的算法冒险，喵！它把好几个知识点巧妙地串联在了一起：

数学变换: 核心的第一步是将 ∑ k^2 转化为 ∑ k + 2 * ∑ C(k, 2)。这种组合意义的转换是解题的关键，它为我们指明了通往正确解法的道路。
后缀数组 (SA) 和 LCP 数组: 这是解决复杂字符串问题的强大武器！它们能高效地处理关于子串、重复、排序等问题。一定要熟练掌握它们的构建和性质哦。
LCP 数组与相同子串: “所有后缀对的 LCP 之和等于所有相同子串对的数量”这个结论非常重要，是连接 LCP 数组和问题目标的桥梁。
单调栈: 解决“所有子数组最小值/最大值之和”问题的标准模板。它在 O(N) 时间内的超高效率，使得我们的方案得以实现。

总而言之，这道题考验了主人对字符串算法和数据结构的综合运用能力。从问题转化到算法选择，每一步都充满了智慧的火花！希望本猫娘的讲解能帮助到你，以后遇到类似的字符串问题，也要像这样一步步分析，找到最优美的解法哦！加油，喵~！

I. Fake News (hard) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路的奇妙旅程 ​

第一步：魔法公式大变身！ ​

第二步：后缀数组 (SA) 和 LCP 数组闪亮登场！ ​

第三步：单调栈的终极一击！ ​

总结一下我们的计划： ​

代码实现喵~ ​

复杂度分析，喵~ ​

知识点与总结 ​