前言

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

小剧场

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

叠甲

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

字符串哈希

字符串比较

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

hash(s)=(\sum_{i=1}^{\lvert s \rvert}s[i]\times base^{n - i})\mod p

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

hash(s)=(\sum_{i=1}^{\lvert s \rvert}s[i]\times base^{i - 1})\mod p

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

子串比较

下面假设我们处理的前缀哈希函数数组为

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)

（类似于双指针的时间复杂度分析），可以通过本题。

正解代码

CPP

#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

的常数。但是较于二分优化也比较快。

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

文章操作

前言

小剧场

叠甲