关于使用字符串哈希求解最长回文子串问题

r1sing · 2025-09-14 13:24:47 · 算法·理论

前言

这个算法相较于 manacher 的空间与时间效率，是并不优秀的。但是它比 manacher 更易懂，学习门槛很低。

小剧场

老师：很多算法都是以人名命名的，manacher 就是一个，再比如说 myt 发明的算法就可以叫 myt 算法。哎呀，这个名字不太好听哈。（笑）把 y 改成 i 就不错了。（笑）
两小时后，“MIT 哈希”诞生了

叠甲

可能这个算法在现在已经有人发现了，但作者并未看到相关文章，如有雷同，纯属巧合（真的真的）。

字符串哈希

字符串比较

字符串哈希其实就是把一个字符串映射成一个自然数，若想比较是否一样，只需判断两串映射的值是否一样即可。“前缀”哈希函数通常是如下形式：

“后缀”哈希函数通常是如下形式：

那么我们现在可以判断两个处理过哈希函数的字符串是否一样，那能不能通过某个字符串的前缀哈希函数或后缀哈希函数，去求得子串的哈希函数呢？答案是可以的。

子串比较

下面假设我们处理的前缀哈希函数数组为 h_i。
对于 hash(s[l\dots r])，根据定义，有 hash(s[l \dots r])= s[l]\times base^{r - l} + \cdots +s[r]，观察到 h[r]=h[l-1] \times base^{r - l + 1} + hash(s[l \dots r])，也就是说 hash(s[l \dots r])= (h[r] - h[l - 1] \times base^{r - l + 1}) \mod p，那么我们就通过预处理的前缀哈希函数数组得到了子串的哈希值，再对哈希值进行比较即可。

关联题目

P3805 【模板】manacher

题目大意

给定一个字符串，求出最长回文子串长度（\lvert s\rvert\le 1.1\times 10^7）。

算法介绍

最朴素的暴力

考虑枚举左右端点 i,j，使用字符串哈希判断 s[i\dots j] 与 s[j\dots i] 是否相等。很明显，它的时间复杂度是 O(\lvert s\rvert ^ 2) 的，非常慢。

二分优化

那么我们发现对于一个左端点，回文串不满足二分的性质，但是对于一个中间点，二分它向外扩展的长度是完全可行的。但是注意到偶数长度的回文串它的中间点不在某个字符上，所以我们可以在原串的每个字符之间插入其它字符，例如 '#'。时间复杂度为 O(\lvert s\rvert\log \lvert s\rvert)，对于一部分的字符串题可以通过，但上题的字符串长度在 10^7 量级上故仍无法通过。

“MYT 哈希”

首先，还是给字符之间插入 '#'，这样避免了偶数长度的情况。注意到，对于每个中间点的长度 len_1,len_2,\dots,len_n 其实我们只关心他们的最大值，即 \max(len_i) 那么我们可以记录一个变量 len，表示截至目前从中心点扩展的最大长度（并非最长回文子串长度）。那么对于目前枚举到的中心点 i 我们发现如果 i 扩展到的长度小于等于 len 是完全没有贡献的（无法更新答案）。那么我们可以再枚举一个 j 表示当中间点 i 向外扩展的长度。如果发现进行这次扩展之后就不是回文子串了，就可以直接停止枚举，否则更新 len 的值。最后的答案应为 2len - 1（对于不同的写法这里也可能是 2len +1）但是由于我们插入了井号，实际答案应该是 \lfloor \frac{2len- 1}{2}\rfloor=len - 1（同样的，不同的写法这里也可能是 \lfloor \frac{2len+ 1}{2}\rfloor=len）。

关于时间复杂度

有人可能看到这是双重循环便认为时间复杂度为 O(\lvert s\rvert ^ 2) 的，实则不然。观察到内层循环的起始点 len 是单调上升的，也就是说对于任意的 i 若它的内层循环的执行次数为 x，则下次循环的最大循环次数也会减少 x-1，那么内层循环最多被执行 2\lvert s\rvert 次，故时间复杂度为 O(\lvert s\rvert)（类似于双指针的时间复杂度分析），可以通过本题。

正解代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN = 22e6 + 5, base = 499, p = 1e9 + 7;
ll n;
string s;
ll h1[MAXN];
ll h2[MAXN];
int bp[MAXN];
ll mod(ll x) {
    return (x % p + p) % p;
}
ll gethash1(ll l, ll r) {
    return mod(h1[r] - h1[l - 1] * bp[r - l + 1] % p);
}
ll gethash2( ll l, ll r) {
    return mod(h2[r] - h2[l - 1] * bp[r - l + 1] % p);
}
bool chk(ll l, ll r) {
    return gethash1(l, r) == gethash2(n - r + 1, n - l + 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    string tmp;
    cin >> tmp;
    for(char it:tmp)
        s.push_back('#'), s.push_back(it);
    s.push_back('#');
    n = s.size();
    s = " " + s;
    bp[0] = 1;
    for(int i = 1; i <= n; i++) {
        h1[i] = (h1[i - 1] * base + s[i]) % p;
        h2[i] = (h2[i - 1] * base + s[n - i + 1]) % p;
        bp[i] = bp[i - 1] * base % p;
    }
    ll len = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = len; i + j - 1 <= n && i - j + 1 >= 1; j++) {
            if(!chk(i - j + 1, i + j - 1))
                break;
            len = max(len, j * 1ll);
        }
    }
    cout << max(len - 1, 1ll);
    return 0;
}

“MYT 哈希”拓展

其实这种字符串哈希可以拓展到一些其他题，比如“找一个字符串中循环节长度为 k 的最长子串”，但其实它在这道题上并不好用，有一道好的练习题，我并不想公开出来（以后应该会）。

总结

经测试，这种算法因为哈希取模等原因，较于 manacher 算法的时间有 \frac{5}{4} 至 5 的常数。但是较于二分优化也比较快。