「ZJOI2020」字符串 题解

问题分析

这个问题要求统计给定区间内本质不同的平方串（形如 $PP$ 的字符串）的数量。平方串也称为"重复串"或"周期串"。

关键挑战

• $n, q \leq 2 \times 10^5$，需要高效算法
• 必须处理本质不同的平方串，相同内容但位置不同视为相同
• 需要支持任意区间查询

算法思路

1. 平方串检测与枚举

核心观察：对于长度 $2L$ 的平方串 $S[1:2L]$，满足 $S[1:L] = S[L+1:2L]$。

代码使用后缀数组和高度数组来高效检测平方串：

for (int len = 1; len <= n; ++len) {
    for (int x = len, y = len + len; y <= n; x += len, y += len) {
        if (s[x] != s[y]) continue;
        int r = A.lcp(x, y), l = B.lcp(n - x + 1, n - y + 1);
        // 计算可能的平方串范围
    }
}

2. 后缀数组技术

构建两个后缀数组：

• A：正序字符串的后缀数组
• B：逆序字符串的后缀数组

用于快速计算最长公共前缀（LCP）：

inline int lcp(int x, int y) {
    x = rk[x], y = rk[y];
    if (x > y) swap(x, y);
    ci k = lg[y - x];
    return min(mn[k][x + 1], mn[k][y - (1 << k) + 1]);
}

3. 哈希去重

使用双哈希确保准确性：

ci B1 = 107, B2 = 109;
ull hs1[N], hs2[N], pw1[N], pw2[N];

对于检测到的平方串，存储其哈希值和位置范围用于去重。

4. 区间查询处理

使用多种数据结构处理查询：

• 树状数组 (BIT)：快速前缀和查询
• 扫描线技术：离线处理区间查询
• 二维数点：处理与区间相关的计数

复杂度分析

• 后缀数组构建：$O(n \log n)$
• 平方串枚举：$O(n \log n)$（调和级数）
• 查询处理：$O((n + q) \log n)$
• 总复杂度：$O((n + q) \log n)$

关键优化技术

1. 调和级数枚举

for (int len = 1; len <= n; ++len) {
    for (int x = len, y = len + len; y <= n; x += len, y += len) {
        // 处理每个可能的平方串起始位置
    }
}

利用 $O(n \log n)$ 的调和级数复杂度枚举所有可能的平方串。

2. 运行合并

合并相邻的平方串运行区间，减少重复处理：

sort(tmp + 1, tmp + t + 1);
for (int i = 1; i <= t; ++i)
    if (i == 1 || tmp[i].l != tmp[i - 1].l || tmp[i].r != tmp[i - 1].r)
        run[++L] = tmp[i];

3. 离线查询优化

将所有查询按右端点排序，使用扫描线处理：

for (int i = 1; i <= q; ++i)
    ql[i] = read(), qr[i] = read(), v2[qr[i]].push_back(i);

算法标签

🏷️ 主要算法

后缀数组 - 高效字符串匹配与LCP计算 哈希技术 - 字符串去重与快速比较 扫描线 - 离线处理区间查询 树状数组 - 快速前缀统计

🏷️ 字符串技术

平方串检测 - 识别重复模式 本质不同子串 - 去重统计 LCP计算 - 快速公共前缀计算

🏷️ 数据结构

RMQ - 区间最小值查询用于LCP BIT - 高效前缀操作 向量存储 - 组织查询和数据

🏷️ 优化策略

调和级数枚举 - 高效检测所有平方串 运行合并 - 减少重复计算 双哈希 - 降低哈希冲突概率 离线处理 - 批量优化查询

这个解决方案通过结合后缀数组、哈希技术和扫描线算法，在 $O((n + q) \log n)$ 的时间内解决了大规模数据的平方串统计问题，体现了现代字符串算法的综合应用。