Manacher

定义

Manacher，它可以在

O(n)

的时间复杂度下，求出一个串的最长回文子串长度或所有回文串个数。

实现步骤

初始化

选择一个中心，向两边扩展，但如果字符串长度为偶数，就不好处理了。

此时，我们可以将字符串里两两字符中间都插入一个同样的字符，字符串开头的左边与结尾的右边也插一个与上面同样的字符，他就可以变成奇数长度的字符串，长度为

2 \times (|s| - 1) + 1

。

CPP

void add() {
	str += '^';
	int len = s.size() - 1;
	for (int i = 0; i <= len; i++) {
		str += '#';
		str += s[i];
	}
	str += "#@";
	m = 2 * len + 1;
	return;
}

核心部分

定义

p_i

为当中心为

i

时的最长回文半径，

R

为最右回文边界 + 1，

mid

为 $R 代表的字符串的回文中心。

定义字符串 s = "ababa"，则初始化后新字符串 str = "#a#b#a#b#a#"，则

p

为：

下标	1	2	3	4	5	6	7	8	9	10	11
$p_i$	1	2	1	4	1	6	1	4	1	2	1

注意，初始时，

p_i

为

1

，因为自己也算回文子串。

接着我们发现，

p

貌似也形成了一个回文数组。所以，我们可以得出以下结论：

当 $i < R$ 时，我们在访问 $i$ 时，我们可以直接取 $p_{2 \times mid - i}$ 的答案，但是，如果 $i + p_i > R$ ，答案只能取 $R - i$ 。所以，结果应该是 $\min(p_{2 \times mid - i}, R - i)$ 。
当 $i \ge R$ 时， $p_i$ 只能等于 $1$ 。

p[i] = ((i < R) ? min(p[2 * mid - i], R - i) : 1);。

接着，

p_i

要向外扩散，以获取最优答案。

即

str_{i + p_i} = str_{i-p_i}

时，

p_i

可以加一（向外扩散一步）。

CPP

while (str[i + p[i]] == str[i - p[i]]) {
    p[i]++;
}

最后，当

i

变得比

R

更优（更大）时，我们需要更新

R

与

mid

。

CPP

if (i + p[i] > R) {
    R = i + p[i], mid = i;
}

若题目要求求最长回文子串长度，因为我们之前加了字符，所以其实最长回文子串长度就是

p_i - 1

。

即 ans = max(ans, p[i] - 1);。

P3805 【模板】manacher

#include <bits/stdc++.h>

using namespace std;

const int N = 3e7 + 10;

string s, str;
int n, m, p[N];

void add() {
	str += '^';
	int len = s.size() - 1;
	for (int i = 0; i <= len; i++) {
		str += '#';
		str += s[i];
	}
	str += "#@";
	m = 2 * len + 1;
	return;
}

void manacher() {
	int R = 0, mid = 0, ans = 0;
	for (int i = 1; i <= m; i++) {
		p[i] = ((i < R) ? min(p[2 * mid - i], R - i) : 1);
		while (str[i + p[i]] == str[i - p[i]]) {
			p[i]++;
		}
		if (i + p[i] > R) {
			R = i + p[i], mid = i;
		}
		ans = max(ans, p[i] - 1);
	}
	cout << ans;
} 

signed main() {
	cin >> s;
	add(), manacher();
	return 0;
}

P3501 [POI 2010] ANT-Antisymmetry

向外扩展的条件是：一个

0

一个

1

。我们可以直接异或，特判双为字符情况即可。

CPP

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3e6 + 10;

string s, str;
int n, m, p[N];

void add() {
	str += '^';
	for (int i = 0; i < n; i++) {
		str += '#';
		str += s[i];
	}
	str += "#@";
	m = 2 * n + 1;
	return;
}

bool check(char x, char y) {
	return (((x - '0') ^ (y - '0')) == 1) || (x == '#' && y == '#');
}

void manacher() {
	int R = 0, mid = 0, ans = 0;
	for (int i = 1; i <= m; i += 2) {
		p[i] = ((i < R) ? min(p[2 * mid - i], R - i) : 1);
		while (check(str[i - p[i]], str[i + p[i]])) {
			p[i]++;
		}
		if (i + p[i] > R) {
			R = i + p[i], mid = i;
		}
		ans += (p[i] - 1) / 2;
	}
	cout << ans;
	return;
} 

signed main() {
	cin >> n >> s;
	add(), manacher();
	return 0;
}

文章操作

定义