AllwithPairs - 题解

标签与难度

标签: 字符串, 字符串哈希, KMP, 前缀函数, 贡献法, 差分思想难度: 2200

题目大意喵~

主人你好呀~！这道题是关于字符串匹配的呐。

我们有 $n$ 个字符串 $s_1, s_2, \ldots, s_n$ 。首先，题目定义了一个函数 $f(s, t)$ ，它的值是这样一个最大的整数 $i$ ：字符串 $s$ 的长度为 $i$ 的前缀，和字符串 $t$ 的长度为 $i$ 的后缀是完全相同的。如果不存在这样的 $i$ ，那么 $f(s, t) = 0$ 。

举个例子，如果 $s = \text{"ababa"}$ ， $t = \text{"zzaba"}$ ，那么 $s$ 的前缀 "aba" 和 $t$ 的后缀 "aba" 是匹配的，并且这是最长的匹配，所以 $f(s, t) = 3$ 呢！

我们的任务就是，计算所有字符串对 $(s_i, s_j)$ 的 $f$ 函数值的平方和，也就是这个式子：

\sum_{i=1}^{n}\sum_{j=1}^{n}f(s_i, s_j)^2

最后结果要对 $998244353$ 取模哦。

解题思路分析

看到这个双重求和 $\sum\sum$ 和一个复杂的函数 $f$ ，直接暴力计算肯定是不行的说。如果我们枚举所有 $n \times n$ 对字符串，再对每一对都去计算 $f(s_i, s_j)$ ，那时间复杂度会爆炸的，喵呜~ (´; ω ;`)

所以，我们需要一种更聪明的办法！这种求和问题，一个常见的思路就是贡献法。我们不直接去算每个 $f(s_i, s_j)^2$ ，而是去考虑每个可能的部分是怎么对最终答案产生贡献的。

但是 $f(s_i, s_j)$ 里面有个 "最大" 的限制，处理起来很麻烦。这时候，一个神奇的数学小技巧就派上用场啦！对于任何一个正整数 $L$ ，我们有：

L^2 = \sum_{k=1}^{L} (k^2 - (k-1)^2)

这个式子大家应该都见过吧！它启发我们把 $f(s_i, s_j)^2$ 拆开。

但是，直接这么拆好像没什么用。我们换个思路，看看 KMP 算法里的前缀函数（next 数组或 pi 数组）。对于一个字符串 $P$ ， $next[|P|]$ 表示 $P$ 的最长公共前后缀（不包括 $P$ 本身）的长度。

假设对于一对 $(s_i, s_j)$ ，我们算出来 $f(s_i, s_j) = L$ 。这意味着 $s_i$ 的前缀 $P_L$ 和 $s_j$ 的一个后缀是匹配的。那么， $s_i$ 的另一个更短的前缀 $P_{next[L]}$ （这里 $next$ 是对 $s_i$ 求的）是不是也可能和 $s_j$ 的某个后缀匹配呢？是的！因为 $P_{next[L]}$ 是 $P_L$ 的后缀，而 $P_L$ 又是 $s_j$ 的后缀，所以 $P_{next[L]}$ 也是 $s_j$ 的后缀。

这样，对于一个确定的 $(s_i, s_j)$ ，如果 $f(s_i, s_j) = L$ ，那么所有满足条件（ $s_i$ 的前缀等于 $s_j$ 的后缀）的长度集合就是 $\{L, \text{next}[L], \text{next}[\text{next}[L]], \ldots, 0\}$ 。

最关键的一步来啦！我们发现 $L^2$ 可以像这样被拆解成一个伸缩和 (Telescoping Sum)：

L^2 = (L^2 - (\text{next}[L])^2) + ((\text{next}[L])^2 - (\text{next}[\text{next}[L]])^2) + \ldots

这个式子最后会把中间项全部消掉，只剩下 $L^2 - 0^2 = L^2$ 。

这简直是天赐的礼物喵！它把对一个 $(s_i, s_j)$ 的贡献 $f(s_i, s_j)^2$ 拆成了一系列 $(k^2 - (\text{next}[k])^2)$ 形式的项的和。

现在，我们可以再次转换求和的顺序。我们不再枚举 $(s_i, s_j)$ ，而是枚举 $s_i$ 和它的每个前缀长度 $k$ 。对于一个固定的 $s_i$ 和一个前缀 $P_k$ （长度为 $k$ ），我们考虑它产生的贡献项 $(k^2 - (\text{next}[k])^2)$ 。这个项会被计算多少次呢？根据伸缩和的原理，它只会在那些满足“ $s_i$ 的前缀 $P_k$ 是 $s_j$ 的后缀”的配对 $(s_i, s_j)$ 中被计算。

所以，我们只需要数出来，有多少个 $s_j$ 拥有 $P_k$ 这个后缀。设这个数量为 count(P_k)。那么，对于一个固定的 $s_i$ ，它的总贡献就是：

\sum_{k=1}^{|s_i|} \text{count}(P_k) \times (k^2 - (\text{next}[k])^2)

把所有 $s_i$ 的贡献加起来，就是最终答案啦！

\text{TotalAns} = \sum_{i=1}^{n} \sum_{k=1}^{|s_i|} \text{count}(P_k) \times (k^2 - (\text{next}[k])^2)

好耶！问题一下就清晰了！我们的算法步骤就是：

预处理后缀计数：遍历所有输入的字符串 $s_j$ ，把它们的每一个后缀都取出来。用字符串哈希将这些后缀转换成数字，然后用一个 unordered_map 来统计每个哈希值（也就是每种后缀）出现的次数。
计算最终答案：
- 遍历每一个字符串 $s_i$ 。
- 对 $s_i$ 计算出它的 KMP 前缀函数（pi 数组）。
- 再次遍历 $s_i$ 的所有前缀 $P_k$ （从长度 $1$ 到 $|s_i|$ ）。
- 对每个 $P_k$ ，计算出它的哈希值，然后从第一步的 map 中查出 count(P_k)。
- 根据公式，把 count(P_k) * (k^2 - (pi[k])^2)累加到总答案中。
- 注意取模运算哦！

这样，我们用 $O(\sum |s_i|)$ 的时间就解决了这个问题，是不是很高效呀，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码！变量名和注释都很清楚，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// 定义一个比较大的质数作为模数
const int MOD = 998244353;
// 使用 unsigned long long 来防止哈希冲突，效果通常不错
using ull = unsigned long long;

// 字符串哈希的基数，选一个常见的素数
const ull BASE = 233;

// 预计算的 BASE 的幂，用于快速计算哈希值
vector<ull> p_pow;
const int MAX_TOTAL_LEN = 1000005;

// 预计算 BASE 的幂
void precompute_powers() {
    p_pow.resize(MAX_TOTAL_LEN);
    p_pow[0] = 1;
    for (int i = 1; i < MAX_TOTAL_LEN; ++i) {
        p_pow[i] = p_pow[i - 1] * BASE;
    }
}

// KMP 算法的核心：计算前缀函数 (pi 数组)
// pi[i] 表示 s[0...i] 的最长公共前后缀的长度
vector<int> calculate_pi(const string& s) {
    int n = s.length();
    vector<int> pi(n);
    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;
}

int main() {
    // 优化输入输出，让程序跑得快一点~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute_powers();

    int n;
    cin >> n;

    vector<string> all_strings(n);
    // 使用 unordered_map 提高查询效率
    unordered_map<ull, int> suffix_counts;

    // --- 第一步：预处理所有后缀的出现次数 ---
    for (int i = 0; i < n; ++i) {
        cin >> all_strings[i];
        int len = all_strings[i].length();
        ull current_suffix_hash = 0;
        // 从后往前遍历，计算所有后缀的哈希值
        for (int j = len - 1; j >= 0; --j) {
            // hash(c + s) = c * p^|s| + hash(s)
            current_suffix_hash = current_suffix_hash * BASE + (all_strings[i][j] - 'a' + 1);
            suffix_counts[current_suffix_hash]++;
        }
    }

    long long total_ans = 0;

    // --- 第二步：遍历每个字符串，计算其贡献 ---
    for (const string& s : all_strings) {
        int len = s.length();
        if (len == 0) continue;

        // 计算当前字符串 s 的 pi 数组
        vector<int> pi = calculate_pi(s);

        ull current_prefix_hash = 0;
        // 从前往后遍历，计算所有前缀
        for (int k = 0; k < len; ++k) {
            // hash(s + c) = hash(s) * p + c
            current_prefix_hash = current_prefix_hash * BASE + (s[k] - 'a' + 1);

            // 查找这个前缀作为后缀出现的次数
            long long count = 0;
            if (suffix_counts.count(current_prefix_hash)) {
                count = suffix_counts[current_prefix_hash];
            }

            // k+1 是当前前缀的长度
            long long k_len = k + 1; 
            // pi[k] 是最长公共前后缀的长度
            long long pi_len = pi[k]; 

            // 计算 k^2 - pi[k]^2
            long long term = (k_len * k_len % MOD - pi_len * pi_len % MOD + MOD) % MOD;
            
            // 累加贡献
            total_ans = (total_ans + count * term) % MOD;
        }
    }

    cout << total_ans << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(\sum |s_i|)$ 设所有字符串的总长度为 $L_{total} = \sum_{i=1}^{n} |s_i|$ 。
1. 预计算哈希的幂次： $O(L_{total})$ 。
2. 统计所有后缀的哈希值：对于每个字符串 $s_j$ ，我们需要 $O(|s_j|)$ 的时间来计算其所有后缀的哈希值并存入 unordered_map。总时间是 $O(\sum |s_j|) = O(L_{total})$ 。
3. 计算最终答案：对于每个字符串 $s_i$ ，计算 pi 数组需要 $O(|s_i|)$ ，遍历其前缀并计算贡献也需要 $O(|s_i|)$ 。总时间是 $O(\sum |s_i|) = O(L_{total})$ 。所以，总的时间复杂度是线性的，非常高效哦！
空间复杂度: $O(\sum |s_i|)$
1. 存储所有字符串需要 $O(L_{total})$ 的空间。
2. p_pow 数组需要 $O(L_{total})$ 的空间。
3. suffix_counts 这个 unordered_map 最多会存储 $L_{total}$ 个不同的后缀，所以空间复杂度是 $O(L_{total})$ 。
4. pi 数组在每次循环中只占用 $O(|s_i|)$ 的空间，可以复用。因此，总的空间复杂度也是 $O(L_{total})$ 。

知识点总结

这道题是字符串算法的一次美妙结合，我总结了以下几个关键知识点，喵~

字符串哈希 (Rolling Hash)：这是解决字符串匹配问题的强大武器！通过将字符串映射成一个数字，我们可以在 $O(1)$ 的时间内（经过 $O(L)$ 的预处理后）比较两个子串是否相等，大大提升了效率。
KMP 算法与前缀函数 (pi 数组)：KMP的核心就是pi数组，它记录了字符串每个前缀的“自我相似性”。在这道题里，它巧妙地帮我们建立起了不同长度匹配之间的桥梁，是构造伸缩和的关键。
贡献法与差分思想：当直接求解困难时，不妨换个角度，思考每个基本单元对总答案的贡献。本题中 $L^2 = \sum (k^2 - (k-1)^2)$ 的思想就是一种差分。而最终解法中 $L^2$ 被拆解成 (L^2 - next[L]^2) + ... 的形式，更是将差分的思想运用到了极致，将复杂的“最大值”约束优雅地化解掉了。

希望这篇题解能帮助主人理解这道有趣的题目！如果还有问题，随时可以再来问我哦，喵~ >w<

AllwithPairs - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​