参考资料：有什么浅显易懂的Manacher Algorithm讲解？ - 知乎 (zhihu.com)

背景 / Background

1975年，一个名叫Manacher的人发明了一种用O(N)的时间复杂度来解决“最长回文子串”问题的方法。但是网络上对Manacher本人的介绍却很少见。他最大的贡献就是将回文串算法从O(N ^ 2)优化到O(N)。

算法简介 / Introduce to the Algorithm

Manacher算法是一种字符串算法，是利用“回文串的特殊性质”以及“字符串的奇偶性质”对朴素的字符串匹配算法进行的优化。

算法流程 / The process of the Algorithm

现在有一个字符串S，假设为"abccbca"。

1.将字符串进行“格式化”，在头部 0 和尾部 2 * N + 2，以及中间位置插入特殊字符（字符串S中不存在的特殊字符，比如^ $ # &等等），注意头部和尾部要使用不同的字符。那么S就变成了T ： "$#a#b#c#c#b#c#a#^"，这样无论长度为奇数还是偶数的字符串都会变成奇数长度（2 * N + 1）的。

2.从1开始到2 * N - 1为止 遍历整个字符串 ，如果i < R，也就是说i在C的回文半径中，那么就直接令p[i] = min(R - i, p[i_mirror])，这里的i_mirror也就是i关于C的对称点，即 i_mirror = 2 * C - i。如果i >= R就令p[i] = 1，别担心，接下来的中心拓展会使得p[i]成为正确的值。

3.当然，p[i]可能会大于p[i_mirror]，因为大于R的位置的情况我们是不知道的，所以只需要对i进行一次“中心拓展”就可以。

时间复杂度看似是O(N ^ 2)，实际上是O(N)。

算法实现 / Implementation of the Algorithm

void Manacher(char s[],int N,int p[])
{
	for(int i = 2 * N + 1;i >= 1; -- i)
		s[i] = (i & 1) ? '#' : s[i / 2]; 	
	
	s[0] = '^', s[2 * N + 2] = '$';//将头部和尾部特殊化 
	
	int C = 0, R = 0;//R为右边界开区间
	for(int i = 1;i <= 2 * N + 1; ++ i)
	{
		p[i] = i < R ? min(R - i, p[2 * C - i]) : 1;//
		while(s[i + p[i]] == s[i - p[i]])p[i] ++;
		if(i + p[i] > R)R = i + p[i], C = i;
	}  
}

练习 / Practice

例题：回文串 (nowcoder.com

这道题的数据太小了，用O(N ^ 2)的朴素算法也能过，但是可以自己尝试用manacher写。

代码

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1500;

char s[maxn * 2];
int p[maxn * 2];

void solve()
{
	int N = strlen(s + 1);
	memset(p, 0, sizeof(int) * (2 * N + 2));
    
	for(int i = 2 * N + 1;i >= 1; -- i)s[i] = (i & 1) ? '#' : s[i / 2];
	s[0] = '^', s[2 * N + 2] = '$';
    
	for(int i = 1, C = 0, R = 0;i <= 2 * N + 1; ++ i)
	{
		p[i] = i < R ? min(R - i, p[2 * C - i]) : 1;
        while(s[i + p[i]] == s[i - p[i]])p[i] ++;
        if(i + p[i] > R) R = i + p[i], C = i; 
	}
	printf("%d\n",*max_element(p + 1,p + 2 * N + 2) - 1);
}

signed main()
{
	while(scanf("%s", s + 1) != EOF)solve();
	return 0;
}

例题：最长回文 (nowcoder.com)

这道题本来是要manacher + 二分 + hash的，但是没想到mannacher + 暴力也能过。

代码

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 9;

char s1[maxn * 2], s2[maxn * 2];
int p1[maxn * 2], p2[maxn * 2];

void Manacher(char s[],int N,int p[])
{
	
	for(int i = 2 * N + 1;i >= 1; -- i)
		s[i] = (i & 1) ? '#' : s[i / 2]; 	
	
	s[0] = '^', s[2 * N + 2] = 'S';
	
	int C = 0, R = 0;//R为右边界开区间 
	for(int i = 1;i <= 2 * N + 1; ++ i)
	{
		p[i] = i < R ? min(R - i, p[2 * C - i]) : 1;
		while(s[i + p[i]] == s[i - p[i]])p[i] ++;
		if(i + p[i] > R)R = i + p[i], C = i;
	}
}

void solve()
{
	int N;cin >> N >> s1 + 1 >> s2 + 1;
	
	Manacher(s1, N, p1);
	Manacher(s2, N, p2);

	int ans = 1;
	for(int i = 2;i <= 2 * N + 2; ++ i)
	{
		int tmp = max(p1[i], p2[i - 2]);
		while(s1[i - tmp] == s2[i - 2 + tmp])tmp ++;
		ans = max(ans, tmp - 1);
	}
	printf("%d\n",ans);
}

signed main()
{
	solve();
	return 0;
}