Manacher 入门

前言

~~这个算法真的比 KMP 简单。~~

描述

给定一个长度为

n

的字符串

S

，求字符串

S

的最长回文子串长度。

1. 暴力

可以使用中心扩展法，对于回文串，枚举中心点，在往两端扩展。要分类讨论奇偶性，总复杂度

O(n^{2})

。

给出部分代码。

长度为奇数

CPP

int k = 0;
while(s[i - k] == s[i + k]) k++;

长度为偶数

CPP

int l = 0, r = 1;
while(s[i - l] == s[i + r]) l++, r++;

2. 优化

Part1

可以发现，每次检查回文都会重复计算，于是可以参考 KMP 的思路，跳过已检查过的点。

Part2

在进行中心扩展时，要分类讨论字符串长度的奇偶性。那在 Manacher 中如何避免呢？在字符串

S

中插入一种

S

中没有的字符，可以用 #。

举个例子，把 "abcab" 操作后变成 "#a#b#c#a#b#"。为了防止越界，要在两端加上两个不同的奇怪字符。不同是为了防止检查回文时多匹配。

这种方法是如何避免奇偶性讨论的，可以自行思考。

3. 正式优化

定义数组

P[0...n]

，

P[i]

为以

S[i]

为中心点的最长回文串的半径。

Manacher 的核心思想是“回文的镜像也是回文”。如图，已经求出了

P[C]

。则它左边的阴影部分是以

j

为中心的回文，由于回文是对称的，所以右边的镜像部分

i

与回文

j

相同，那么在计算以

s[i]

为中心时，可以直接从长度

P[j]

开始匹配。然而这只是一种情况，下面是 Manacher 的完整思路。

假设已经求出了

p[0]\sim p[i-1]

，现在求

P[i]

。定义

C

为

p[0]\sim p[i-1]

这些回文串中最大的中心点，

R

为

C

对应的回文串的右端点。那么

R

就等于

C + P[C]

，且

R

是已检查字符串的右端点。通俗的说，

R

左边的都检查过，右边的都没检查。

现在有两种情况。

i \ge R

因为

R

右边的都没检查，所以只能将

P[i]

设为

1

然后进行暴力。

i < R

这种情况，又可以细分为两种小情况。

上文叙述了这种情况，这里仅做补充。如何得知 $j$ 的位置？因为 $\frac{i + j}{2} = C$ ，所以 $j = 2C - i$ 。然后对 $i$ 进行中心扩展即可。 2.当 $j$ 的回文在 $C$ 对应字符串的外部时，那么由图可知， $i$ 可确定的回文也只有 $i$ 到 $R$ 这段了，当然这段长度是 $R-i$ ，所以以这段为基础进行中心扩展即可。

4. 答案

举个例子就明白了：#a#b#b#a# #a#b#c#b#a#

观察可以得到，答案即为半径减一。

5.模板

【模板】manacher & 高手过愚人节

可以先消化完上面的内容再来做。因为上文讲的很清楚了，这里只给出代码。

CPP

void manacher(char *t)
{
	int r = 0, c = 0;
	for(int i = 0;i < n;i++)
	{
		if(i < r) p[i] = min(p[(c << 1) - i], r - i);
		else p[i] = 1;
		while(t[i - p[i]] == t[i + p[i]]) p[i]++;
		if(i + p[i] > r)
		{
			r = i + p[i];
			c = i;
		}
	}
}

6.应用

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

题意很好理解，看到最长回文子串显然可以想到 Manacher。可以观察到双回文子串就是两个回文子串，于是把双回文子串分成两部分。统计以这位为结尾或开头的最长回文子串。这部分可以在中心扩展时维护。答案即为两者相加。

参考代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, ans, p[N << 1], l[N << 1], r[N << 1];
string s, t;
void manacher(string t)
{
	int n = t.size();
	int R = 0, c = 0;
	for(int i = 0;i < n;i++)
	{
		if(i < R) p[i] = min(p[(c << 1) - i], R - i);
		else p[i] = 1;
		l[i - p[i] + 1] = max(l[i - p[i] + 1], p[i] - 1);
		r[i + p[i] - 1] = max(r[i + p[i] - 1], p[i] - 1);
		while(t[i - p[i]] == t[i + p[i]])
		{
			p[i]++;
			l[i - p[i] + 1] = max(l[i - p[i] + 1], p[i] - 1);
			r[i + p[i] - 1] = max(r[i + p[i] - 1], p[i] - 1);
		}
		if(i + p[i] > R)
		{
			R = i + p[i];
			c = i;
		}
	}
}
int main()
{
	cin >> s;
	n = s.size();
	t = "$#"; 
	for(int i = 0;i < n;i++)
	{
		t.push_back(s[i]);
		t.push_back('#');
	}
	t.push_back('&');
	manacher(t);
	n = t.size();
	for(int i = 3;i < n - 2;i++)
		if(t[i] == '#')
			ans = max(ans, l[i] + r[i]);
	cout << ans;
	return 0;
}

7.习题

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

[THUPC2018] 绿绿和串串

回文匹配

文章操作

前言

描述