Manacher

马拉车的用处是求出一个字符串以每个位置为回文中心的最大回文半径。

负面效果是会让字符串每两个字符中间插入一个间隔符，增加代码难度。

马拉车的思想是尽量利用之前求出的信息，用以前的回文推出后面的回文。

当前回文中心如果在以前求出的回文范围内，那当前回文中心可以对称到一个对称点上，在以此为基础扩展，当然，继承的信息不能超过之前求出的回文的右端点。

还是读代码复习比较好。

char a[maxn], s[maxn << 1];
// a 是初始字符串，s 是增加间隔符后的字符串
void manacher()
{
	int mr = 0, mid = 0;			// 当前扩展到的 右端点最右的回文串 的右端点、其回文中心
	for (int i = 1; i < n; i++) // 最后一个字符是休止符
	{
		if (i <= mr)								// i ∈ [mid, mr]
			p[i] = min(p[2 * mid - i], mr - i + 1); // min {p[j], len(i, mr)}
		else
			p[i] = 1; // 自己
		for (; s[i - p[i]] == s[i + p[i]];)
			p[i]++;			   // 尝试继续扩展
		if (i + p[i] - 1 > mr) // 更新 mid 和 mr
		{
			mr = i + p[i] - 1;
			mid = i;
		}
	}
}
void init() // 将字符串中间插入间隔符号，使得回文中心位于字符上
{
	s[0] = s[1] = '#';
	for (int i = 1; i <= n; i++)
	{
		s[i * 2] = a[i];
		s[i * 2 + 1] = '#';
	}
	n = n * 2 + 2;
	s[n] = 0;
}

P4555 [国家集训队] 最长双回文串

记录点 \(i\) 作为左端点时最长的回文子串长度 l[i]，类似地记录 r[i]，要求的时候就对每个间隔符 r[i] + l[i] 就是最大值了。

但这样做只会统计最长回文串长度，还要一步递推求每个点的最大长度。

字符串的题目通常细节很多，需要仔细实现 + 调试。

可以将整个字符串和每个点对应的辅助数组一并输出，并对齐。

printf("%-3d", p[i]); // 位宽三位

UVA11475 Extend to Palindrome

屑题，求完 \(p\) 数组检查有没有回文半径到最右边的回文中心。

P3501 [POI2010] ANT-Antisymmetry

实现细节较多的一道题，思维细节倒是没啥。

就是马拉车的判定回文条件从相等变为相反，然后只能有偶数的子串出现就是了。

/*
大前提：即将扩展的左右端点都在母串内部
扩展条件（满足一个即可）：
1. 左右相等且都为间隔符
2. 左右相反
*/
for (; ((s[i - p[i]] == s[i + p[i]] && s[i - p[i]] == '#') || s[i - p[i]] != s[i + p[i]]) && i - p[i] > 0 && i + p[i] < n;)
{
	p[i]++;
}

P1659 [国家集训队] 拉拉队排练

把符合题意的回文丢进桶里，暴力快速幂即可。

P5446 [THUPC2018] 绿绿和串串

这么多题里唯一一道比较好的题目。

显然翻转过后的串一定是实际意义上的（去除间隔符）奇数长度。

除了最后一步，前面翻转的步骤一定是正好翻转到合法位置的，不能截取前缀。

能翻转的条件（满足一个即可）：

1. 回文半径挨到了字符串末尾

   这样翻转后可以保证原串是翻转串的子串。

2. 回文半径挨到了字符串开头，且其后面子串可以通过翻转的逆操作得到

   这样可以保证翻转后正好是原串的前缀。

字符串题想清楚了才好做，否则会困入细节错误中调不出来。