再学串串（五）：谁会不喜欢可爱的小马（拉车）呢？
因为是赛马娘拉车，所以先于 SA 出来了——绝对不是因为不会 SA 什么的（大嘘）。
可能有点水（）五一集训去了加之回来五一假回来要期中考，再加上最近状态不太好去看心理医生了所以这次含水量可能有点高。
过去的章节
- 再学串串（一）：我真的学会 KMP 了吗？评「clx201022 式的傲慢」
- 再学串串（二）：AC 自动机不是自动 AC 机
- 再学串串（三）：被构造自动机上计数 DP 题吓晕
- 再学串串（四）：后缀是后缀的后缀是后缀的后缀
目前已同步在博客园更新。
第五站：Manacher
为什么叫马拉车呢？因为发明者就是 Manacher，跟 Tarjan 算法[^Tarjan]是 Tarjan 提出的一个道理。
例题：P1723 高手过愚人节。
高手觉得回文串很美观，但回文串美观在哪里呢？
回文基本性质
有一个很简单的定义：设一个字符串
对于回文串，有以下几个美观的性质：
- 一个串是回文串当且仅当它的翻转是它本身，且如果一个串的翻转是一个回文串，那么它自身也是一个回文串。
很显然的基本事实。
- 一个回文串在两端分别加入一个相同的字符后，仍是一个回文串。
显然，在两端分别加入一个字符对
- 一个两端分别加入一个相同的字符后是一个回文串的串，是一个回文串。
还有：
- 在一个回文串
S 中，其对于任意合法的S[l,r] ，设l 的对称点l'=n-l ，r 的r'=n-r' ，则总有S[l,r]_R=S[r',l'] 。
然后你就可以自己推出 Manacher 算法了。
不信？那就来试试看吧！
Re：从零开始的马拉车推导
目标是求主串
抄袭借鉴 KMP 算法（虽然历史上马拉车提出的比 KMP 早），想到从前往后推。因为回文串知道中心的情况下比较好推导，所以存下每一个位置的最长回文子串半径——这样也等价于存下了所有的回文串，因为主串
奇数串和偶数串的本质是一样的，偶数串当作回文中心在中间两个字符中间即可。有些时候会在每两个字符间填充特殊字符以显式地表现这个中心，但这不是必要的。
设当前已求得
考虑当前所有已求得的回文串中蕴含的信息对求
设任意一个已知的
在
注意到在
:::warning
单纯地选取右端点最靠右而不考虑其他元素并不一定是最优的，只是有一个时间复杂度上界保证。
如
https://www.luogu.com.cn/record/276793903
for(int p = 0, i = 1; i <= n; i++)
{
if(p + odd[p] > i) // 至少要能够到吧
{
int ici = 2 * p - i; // 对称过去
odd[i] = min(odd[ici], p + odd[p] - i);
}
while(i - odd[i] >= 1 && i + odd[i] <= n && s[i - odd[i]] == s[i + odd[i]]) odd[i]++;
if(!p || i + odd[i] > p + odd[p]) p = i;
ans = max(ans, odd[i] * 2 - 1);
}
for(int p = 0, i = 1; i <= n; i++)
{
if(p + even[p] > i) // 至少要能够到吧
{
int ici = 2 * p - i; // 对称过去
even[i] = min(even[ici], p + even[p] - i);
}
while(i - even[i] - 1 >= 1 && i + even[i] <= n && s[i - even[i] - 1] == s[i + even[i]]) even[i]++;
if(!p || i + even[i] > p + even[p]) p = i;
ans = max(ans, even[i] * 2);
}与
https://www.luogu.com.cn/record/276824692
for(int p = 0, i = 1; i <= n; i++)
{
if(p + odd[p] > i) // 至少要能够到吧
{
int ici = 2 * p - i; // 对称过去
odd[i] = min(odd[ici], p + odd[p] - i);
}
while(i - odd[i] >= 1 && i + odd[i] <= n && s[i - odd[i]] == s[i + odd[i]]) odd[i]++;
if(!p || i + odd[i] >= p + odd[p]) p = i;
ans = max(ans, odd[i] * 2 - 1);
}
for(int p = 0, i = 1; i <= n; i++)
{
if(p + even[p] > i) // 至少要能够到吧
{
int ici = 2 * p - i; // 对称过去
even[i] = min(even[ici], p + even[p] - i);
}
while(i - even[i] - 1 >= 1 && i + even[i] <= n && s[i - even[i] - 1] == s[i + even[i]]) even[i]++;
if(!p || i + even[i] >= p + even[p]) p = i;
ans = max(ans, even[i] * 2);
}都符合条件，但经实测，前者总是比后者更优。
:::
把已知信息都用完之后就只能根据性质
:::info[证明]
:::
求
:::success[马拉车到~~~]
#include<bits/stdc++.h>
using namespace std;
const int maxlen = 1e7;
string s;
int odd[maxlen + 1], even[maxlen + 1];
// odd 回文串半径（向上取整）
void solve()
{
cin >> s;
int n = s.size();
int ans = 0;
s = " " + s;
memset(odd, 0, sizeof odd);
memset(even, 0, sizeof even);
for(int p = 0, i = 1; i <= n; i++)
{
if(p + odd[p] > i) // 至少要能够到吧
{
int ici = 2 * p - i; // 对称过去
odd[i] = min(odd[ici], p + odd[p] - i);
}
while(i - odd[i] >= 1 && i + odd[i] <= n && s[i - odd[i]] == s[i + odd[i]]) odd[i]++;
if(!p || i + odd[i] > p + odd[p]) p = i;
ans = max(ans, odd[i] * 2 - 1);
}
for(int p = 0, i = 1; i <= n; i++)
{
if(p + even[p] > i) // 至少要能够到吧
{
int ici = 2 * p - i; // 对称过去
even[i] = min(even[ici], p + even[p] - i);
}
while(i - even[i] - 1 >= 1 && i + even[i] <= n && s[i - even[i] - 1] == s[i + even[i]]) even[i]++;
if(!p || i + even[i] > p + even[p]) p = i;
ans = max(ans, even[i] * 2);
}
cout << ans << endl;
}
int main()
{
int n;
cin >> n;
while(n--) solve();
return 0;
}:::
友链
- 博客园同步更新~
创作声明
本文遵循 CC BY-NC-SA 4.0 协议。
保证本文未使用任何 AI 工具辅助创作。
转载例如下：
[原文](https://www.luogu.com.cn/article/8bh9pjuk)作者为 [clx201022](https://www.luogu.com.cn/user/552688)，转载人保证会遵循 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans) 协议：以适当的方式署名，不以盈利为目的进行转载，并以相同方式共享此文。
[^Tarjan]: 你还记得有多少算法叫 Tarjan 算法吗？
[^fanzhaun]: 设