记录
23:39 2024-2-5
manacher算法，是可以在O(n)时间计算回文串的算法
具体思路可以查看Manacher
非常有意思的算法。利用了俩个数组d1[i] 和 d2[i] 分别来记录以位置 i 为中心的长度为奇数和长度为偶数的回文串个数
这里利用了回文串个数也即以i为中心的最长回文串的半径长度 (半径长度指的是 i -> r)
同时利用l，r不断记录r最大的回文串，r越大，对于i来说越容易利用到前面获得的信息
就是利用 i 和 l + r - i 这俩个在[l,r]中对称的位置，感觉听说过的字符串算法不少都是利用前面的信息
(KMP、ac自动机还有刚看到的Z函数(扩展KMP)，好像是废话 -，-)
(我还想需不需要考虑l的位置，但其实选择了最大的r后，l就必须选这个了)
代码也来自 OIwiki
点击查看代码
// 计算d1[i] 奇字符串
vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
// 计算d2[i] 偶字符串
vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
k++;
}
d2[i] = k--;
if (i + k > r) {
l = i - k - 1;
r = i + k;
}
}
// 统一处理