[字符串匹配算法]Manacher算法详解

发布于 2022-04-28  1237 次阅读


参考资料:有什么浅显易懂的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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-11-02