Manacher

[Ir1d]

https://oi-wiki.org/string/manacher/

[Lutra-Fs]

全文引用洛咕日报#80？

[Lutra-Fs]

建议修改页面使之适应Wiki风格

[Ir1d]

@ZhangBo1191 作者是同一个人，谢谢

[Ir1d]

@ZhangBo1191 本页面内容已经重写了，谢谢提醒

[Lagos-Ren]

有点神奇

[minghu6]

确实和Z函数的算法思路完全一样，看懂了一个，另一个马上就明白了。

代码和z函数统一风格的话是：

奇数回文

vector<int> d1(n);
fill(d1.begin(), d1.end(), 1);
for(int i = 0, l = 0, r = 0; i < n; i++) {
    if (i <= r) d1[i] = min(d1[l + r - i], r - i + 1);
    while (d1[i] < i + 1 && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) ++d1[i];
    if (i + d1[i] - 1 > r) l = i + 1 - d1[i]; r = i + d1[i] - 1;
}

偶数回文

vector<int> d2(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {  // 偶数回文要求至少有s[i], s[i - 1] 存在
    if (i <= r) d2[i] = min(d2[l + r - i + 1], r - i + 1);
    while (d2[i] < i && i + d2[i] < n && s[i - d2[i] - 1] == s[i + d2[i]]) ++d2[i];
    if (i + d2[i] - 1 > r) l = i - d2[i]; r = i + d2[i] - 1;
}

我觉得哪怕是原型算法里最好也不要随便用负值，因为实践里要都要换成 unsigned

[CamberLoid]

代码和英文翻译版似乎不一样，请留意 @Ir1d
（暂时不开issue

[lucheng2]

计算d1的代码有个地方有问题：d1[i] = k--;，应该是d1[i] = --k;，这样才能过。统一处理的思想挺有用的，厉害。

[shenruzhang]

这个应该没问题的吧，不知道您是哪出了问题

[yan-gui-lai]

@lucheng2
计算d1的代码有个地方有问题：d1[i] = k--;，应该是d1[i] = --k;，这样才能过。统一处理的思想挺有用的，厉害。

改不改都一样好吧，只是一个理解d1[i]的方式

[limuy2022]

神奇的复杂度

[ljy2009]

https://oi-wiki.org/string/hash/#%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2
这里说字符串hash是O(n)的