---

「PA 2018」Palindrom 题解

问题分析

我们需要判断一个字符串是否是回文串，但有两个关键约束：

1. 内存限制严格：只有 4 MiB
2. 字符串长度可能未知：$n$ 可能为 0

代码思路解析

这是一个基于哈希的在线算法，通过计算正向哈希和反向哈希来判断回文。

核心数学原理

哈希函数设计：

• 正向哈希：$H = \sum_{i=0}^{n-1} s[i] \times B^i \mod P$
• 反向哈希：$iH = \sum_{i=0}^{n-1} s[i] \times B^{-i} \mod P$

对于回文串，应该有 $H \times B^{n-1} = iH \times B^{n-1}$，即 $H = iH$

算法流程

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;  // 读取n（可能为0）
    char ch;
    n = 0;     // 重置n，自己统计长度
    int H = 0, iH = 0;  // 正向哈希和反向哈希
    int u = 1, v = 1;   // B的幂次和B^{-1}的幂次
    
    while (cin >> ch) {
        ++n;
        (H += ch * u) %= P;      // 正向哈希：s[i] * B^i
        (iH += ch * v) %= P;     // 反向哈希：s[i] * B^{-i}
        u = u * B % P;           // u = B^i
        v = v * iB % P;          // v = B^{-i}
    }
    
    iH = iH * qpow(B, n - 1) % P;  // 调整反向哈希的尺度
    
    if (H == iH)
        cout << "TAK\n";
    else
        cout << "NIE\n";
}

算法正确性证明

定理：对于回文串 $s$，有 $H = iH \times B^{n-1}$。

证明： 设字符串为 $s_0s_1\dots s_{n-1}$，如果是回文串，则 $s_i = s_{n-1-i}$。

正向哈希：

$$H = \sum_{i=0}^{n-1} s_i B^i$$

反向哈希（调整前）：

$$iH' = \sum_{i=0}^{n-1} s_i B^{-i}$$

调整后：

$$iH = iH' \times B^{n-1} = \sum_{i=0}^{n-1} s_i B^{n-1-i} $$

由于 $s_i = s_{n-1-i}$，所以：

$$iH = \sum_{i=0}^{n-1} s_{n-1-i} B^{n-1-i} = \sum_{j=0}^{n-1} s_j B^j = H $$

复杂度分析

• 时间复杂度：$O(n)$，单次遍历字符串
• 空间复杂度：$O(1)$，只使用常数个变量
• 内存使用：几个整型变量，远小于 4 MB

内存优化分析

该算法的精妙之处在于：

1. 在线处理：逐个字符读取，不存储整个字符串
2. 常数空间：只维护哈希值和幂次，与字符串长度无关
3. 适应未知长度：自动统计字符串长度

示例验证

样例1：kajak ($n=5$)

计算过程：

• 逐个字符处理，计算 $H$ 和 $iH$
• 最终 $H = iH \times B^4$，输出 TAK

样例2：kanu ($n=0$)

计算过程：

• 自动统计长度 $n=4$
• $H \neq iH \times B^3$，输出 NIE

算法优势

1. 严格满足内存限制：$O(1)$ 空间复杂度
2. 处理未知长度：自动统计字符串长度
3. 高效：$O(n)$ 时间复杂度
4. 正确性：基于数学原理，正确判断回文

潜在问题

哈希冲突：虽然概率极低，但理论上可能存在不同字符串哈希值相同的情况。不过对于本题的数据规模，可以认为是正确的。

算法标签

• 字符串处理
• 哈希算法

---

总结

这道题的解法展示了在严格内存限制下的巧妙算法设计：

1. 利用哈希函数避免存储整个字符串
2. 通过数学变换实现回文判断
3. 在线处理适应未知长度情况

该算法在时间复杂度、空间复杂度和正确性之间取得了很好的平衡，是处理大规模数据内存限制问题的典型范例。