牛客23多校第二场G - Link with Centrally Symmetric Strings
- Manacher,回文串的性质
- https://ac.nowcoder.com/acm/contest/62249/I
题意
给出一个长度为 的字符串 ，问 是否能表示成一个或若干个好回文串拼接而成的形式。即判断： 是否成立。
好回文串的定义如下：
- 由字符 ,,, 之一组成的长度为 的字符串是好回文串。
- 或 或 或 或 或 或 或 或 或 都是好回文串，其中 是一个好回文串。
思路
先判断一个字符串是否为好回文串。
可以改造 Manacher 算法，直接更改 Manacher 算法的匹配规则即可。
int mid = 0;
int limR = 0;
for (int i=1; i<=str_n; i++)
{
if(i < limR)
p[i] = min(p[mid-(i-mid)], limR-i);
else
p[i] = 0;
//直接更改 Manacher 算法的匹配规则即可。
//while (str[ i+p[i] ] == str[ i-p[i] ])
while (str[ i+p[i] ] == rev(str[ i-p[i] ]))
p[i] ++;
if(i+p[i] > limR)
{
mid = i;
limR = i+p[i];
}
}
直接更改 Manacher 算法的匹配规则的正确性
注意此代码：
if(i < limR)
p[i] = min(p[mid-(i-mid)], limR-i);
此代码的作用是：如果当前回文中心 被包含在前面某个延伸到最右方的回文串（回文中心是 ，延伸到最右方的位置为 ）中，那么可以将 以 为对称中心，对称到 。
即为当前回文中心 的回文串长度的最小值。
注意到， 和 ， 和 ， 和 都是好回文串。
如果以 为回文中心的回文串是 的形式，那么以 为回文中心的回文串就一定是 的形式。
如果只有 是好回文串，而 不是好回文串，那么就不能直接更改 Manacher 算法的匹配规则。
换句话说，无论匹配规则是什么，只要满足正串是回文串 反串是回文串，那么就一定能用 Manacher 算法，否则就一定不能用。
如何判断 是否能表示成好回文串拼接而成的形式
请回顾：
- 如果 是一个回文串，那么 一定是一个回文串。并且如果 是一个回文串，那么 一定也是一个回文串。
- 如果 是一个回文串，那么 的反串也是回文串。
但是，可以从前往后扫描字符串。
记之前某个延伸到最右方的回文串的延伸到最右方的位置为 。
对于位置 ，如果以 为回文中心的回文串最左边能延伸到的位置 ，说明以 为回文中心的回文串能将 及其之前的位置覆盖完全，此时更新 为 。
如果最后 ，说明回文串可以将整个字符串完全覆盖，否则不行。
例如：
字符串 ，可以有这样的划分：。
但是如果按照上述方法划分，则划分的字符串为：。
不难发现，在从左往右扫描的过程中，如果发现一段回文串能覆盖之前的，那么是可以贪心的选择的。因为如果当前回文串被包含在了后面的更长的回文串中，那么后面会有一段与之对称的回文串。
京公网安备 11010502036488号