.svg)
今天来水一篇题解（毕竟再不写博客就没人看了
题目分析
- 优秀拆分的定义：对于一个字符串，若能拆分成 AABB 的形式，其中 A 和 B 是任意非空字符串，这种拆分即为优秀拆分。例如，“aabaabaa” 可拆分为 A = “aab”，B = “a” 或者 A = “a”，B = “baa” 等形式；而 “abaabaa” 不存在优秀拆分。
- 输入输出要求：输入包含多组数据，第一行整数 T 表示数据组数。后续 T 行，每行是一个仅由英文小写字母构成的字符串 S。输出对应 T 行，每行一个整数，表示字符串 S 所有子串的优秀拆分总数。
- 数据范围：数据组数 T 满足 1 ≤ T ≤ 10，字符串 S 的长度 n 在不同测试点有不同限制，从 10 到 30000 不等，部分测试点字符串中所有字符相同。
算法思路
- 预处理哈希值：对输入字符串预处理，计算每个前缀的哈希值存于数组 h 中，同时计算 P 的幂次存于数组 p 中，便于后续快速计算任意子串的哈希值。
- 判断 AA 形式子串：枚举子串长度（限定为偶数）和起始位置，利用哈希值快速判断子串是否为 AA 形式。若是，则分别记录以该子串起始位置开头的 AA 型子串数量（存入 startAA 数组）和以该子串结束位置结尾的 AA 型子串数量（存入 endAA 数组）。
- 计算优秀拆分总数：遍历字符串，以每个位置为分割点，将该位置之前结束的 AA 型子串数量和之后开始的 AA 型子串数量相乘并累加，得到最终的优秀拆分总数。
C++ 代码实现
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int P = 131;
// 计算字符串 s 中所有子串的优秀拆分总数
int countExcellentSplits(const string& s) {
int n = s.length();
vector<int> startAA(n, 0); // 记录以每个位置开头的 AA 型子串的数量
vector<int> endAA(n, 0); // 记录以每个位置结尾的 AA 型子串的数量
vector<ULL> h(n + 1, 0); // 存储前缀哈希值
vector<ULL> p(n + 1, 0); // 存储 P 的幂次
// 预处理前缀哈希值和 P 的幂次
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s[i - 1];
}
// 计算子串 [l, r] 的哈希值
auto getHash = [&](int l, int r) {
return h[r + 1] - h[l] * p[r - l + 1];
};
// 枚举所有可能的 AA 型子串
for (int len = 2; len <= n; len += 2) {
for (int i = 0; i + len - 1 < n; i++) {
int mid = i + len / 2 - 1;
// 利用哈希值判断是否为 AA 型子串
if (getHash(i, mid) == getHash(mid + 1, i + len - 1)) {
startAA[i]++;
endAA[i + len - 1]++;
}
}
}
// 计算优秀拆分的总数
int ans = 0;
for (int i = 0; i < n - 1; i++) {
ans += endAA[i] * startAA[i + 1];
}
return ans;
}
int main() {
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
cout << countExcellentSplits(s) << endl;
}
return 0;
}
代码详解
- 预处理部分：通过循环计算前缀哈希值 h 和 P 的幂次 p，为后续子串哈希值的计算做准备。
- getHash 函数：这是一个 lambda 函数，用于快速计算子串 [l, r] 的哈希值。借助前缀哈希值和 P 的幂次，能以 O (1) 的时间复杂度得到子串的哈希值。
- 枚举 AA 型子串：两层循环枚举子串的长度和起始位置，利用 getHash 函数判断子串是否为 AA 形式。如果是，更新 startAA 和 endAA 数组。
- 计算优秀拆分总数：遍历字符串，以每个位置为分割点，将该位置前后的 AA 型子串数量相乘并累加，从而得到优秀拆分的总数。
性能分析
- 时间复杂度：整体时间复杂度为 O (Tn²)，T 为数据组数，n 为字符串长度。主要耗时操作是枚举所有可能的 AA 型子串，这部分操作的时间复杂度为 O (n²)。在处理大规模数据时，该算法可能会面临时间挑战，当前有一个测试点出现 TLE（超时）情况。
- 空间复杂度：算法使用了几个辅助数组，如 startAA、endAA、h 和 p，其大小都与字符串长度 n 相关，因此空间复杂度为 O (n) 。
虽然当前代码在一个测试点存在超时问题，但哈希算法的引入已经大大优化了子串比较的效率。后续可考虑进一步优化枚举策略或采用更高效的数据结构来解决剩余的性能瓶颈。
评论区