马拉车算法

Problems Website

【模板】manacher算法
Solution
这道题要判断最大回文串的长度，根据数据范围，朴素算法肯定会超时，于是我们要用到一种新算法，manacher算法（马拉车算法）。
通过观察，我们发现回文串按长度可分为两种，一种为奇数串，一种为偶数串，奇数串的回文中心为一个，而偶数串的回文中心有两个，例如
1
2
3
4
ABCBA
奇数串，回文中心为C
ABCCBA
偶数串，回文中心为CC
我们可以将上面的两个串变为
1
2
~|A|B|C|B|A|
~|A|B|C|C|B|A|
就可以保证对称中心为一个字符。
下面是一些回文串的性质，内容为转载，来自洛谷
- 对于一个回文串，有且仅有一个对称中心。且叫它回文对称中心。
- 在一个回文串内，任选一段区间 X ，一定存在关于”回文对称中心“对称的一个区间，且把这个区间叫做关于区间X的对称区间。
- 区间和对称区间一定全等。（ 1）(十分显然)
- 由（1）得 ,若一个区间的对称区间是回文串，这个区间必定是一个回文串。在大的回文串内，它们回文半径相等。 (2)然而我们通过确定关系预先得到的回文半径，它的数值，必定小于等于这个位置真实的回文串半径。（十分显然）
  以上内容可以帮助理解马拉车算法，也可以解释马拉车算法为何有很优秀的复杂度。

马拉车算法的基本思路：根据(2)，我们只需要记录每个回文串的回文中心以及对应的回文半径，我们设p[i]为以字符i为回文中心的最大回文串的半径，mid为已知回文串中最右侧回文串的回文中心，r为已知回文串中最右侧回文串的最右端，转移过程如下

if i的对称点为j，且mid <= i < r
	p[i] = min(p[mid*2-i], r-i);
//因为(i+j)/2 = mid
//移项得
//j = 2 * mid - i
// r-i为我们已知的范围剩余长度
else
	p[i] = 1;

最后答案即为max(p[i] - 1)，因为p[]存的是回文串的半径。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
char s[11000010 << 1];
int cnt = 1, r, mid, ans;
int p[11000010 << 1];
void sc() {
	char cch = gc;
	s[0] = '~'; s[1] = '|';
	while(cch < 'a' || cch > 'z')
		cch = gc;
	while(cch >= 'a' && cch <= 'z') {
		s[++cnt] = cch;
		s[++cnt] = '|';
		cch = gc;
	}
}
int main() {
	sc();
	for(int i = 1; i <= cnt; i++) {
		if(p[i] < r)
			p[i] = min(r - i, p[(mid << 1) - i]);
		else
			p[i] = 1;
		while(s[i + p[i]] == s[i - p[i]]) //为了防止下标溢出，我们才在字符串最前面加了'~' 
			p[i]++;
		if(p[i] + i> r) //更新 
			r = p[i] + i, mid = i;
		if(p[i] > ans)
			ans = p[i] - 1;
	}
	printf("%d\n", ans);
	return 0;
}

rp++

Problems Website

Solution

Code