526互联

Manacher

发布时间 2023-12-21 18:57:42作者: viewoverlook

Manacher

最长回文子串问题

  • 一个字符串从左往右看和从右往左看是一样的叫回文串
  • 回文串可以按长度的奇偶性分为奇数长度和偶数长度回文串
  • 最长回文子串指对于任意一个给定的字符串，我们要求出这个字符串的最长回文子串

暴力 \(O(n^3)\)

枚举所有子串，检查当前枚举到的子串是否为回文串，最后从符合条件的子串中找出最长的即可

Manacher \(O(n)\)

Mancher算法可以求出从字符串任意位置出发，往两边最远能够扩展出的回文子串的长度

去除子串长度奇偶性的技巧:对于字符串s,使用一个s中不存在的字符把s中的字符隔开(开头结尾也要加)

例如，字符串abacc变为#a#b#a#c#c#

然后再来求新得到的串中奇数长度的最长回文子串,知道了新得到的最长回文子串,s最长回文子串只需要把新得到的串长度取一半即下文所得到所说的回文半径p[i]。

算法流程

新得到的字符串s,我们的目标是求出从它的任意位置i出发,往两边最远能够扩展出的回文子串的长度(往一边能够扩展的字符数即为从i开始的最大回文半径,记作p[i],p[i]包括自己所以最小是1)

p[i]的维护：从左到右一个一个计算p[i]值
假设现在算p[i]，和之前扩展kmp类似，维护一个到目前为止R的最大区间[L,R]，L=M-p[M]+1(M<i), R=M+p[M]-1

若i<=R,
1.

算法模板:

const int N=1e6+10;
char Ma[N<<1];
char s[N];
int Mp[N<<1];
void Manacher(char s[],int len)
{
	int l=0;
	Ma[l++]='$';
	Ma[l++]='#';
	for(int i=0;i<len;i++)
	{
		Ma[l++]=s[i];
		Ma[l++]='#';
	}
	Ma[l]=0;
	int mx=0,id=0;
	for(int i=0;i<l;i++)
	{
		Mp[i]=mx>i?min(Mp[(id<<1)-i],mx-i):1; //确定以当前位置为中心的最长回文串是否在已确定的有边界内
		while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;
		if(i+Mp[i]>mx)
		{
			mx=i+Mp[i];
			id=i;
		}
	}
}
int main()
{
	scanf("%s",s);
	int len=strlen(s);
	Manacher(s,len);
	int ans=0;
	for(int i=0;i<(len<<1)+2;i++) ans=max(ans,Mp[i]-1);
	printf("%d\n",ans);

	return 0;
}

例题

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=1e6+10;
char Ma[N<<1];
char s[N];
int Mp[N<<1];
void Manacher(char s[],int len)
{
	int l=0;
	Ma[l++]='$';
	Ma[l++]='#';
	for(int i=0;i<len;i++)
	{
		Ma[l++]=s[i];
		Ma[l++]='#';
	}
	Ma[l]=0;
	int mx=0,id=0;
	for(int i=0;i<l;i++)
	{
		Mp[i]=mx>i?min(Mp[(id<<1)-i],mx-i):1; //确定以当前位置为中心的最长回文串是否在已确定的有边界内
		while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;
		if(i+Mp[i]>mx)
		{
			mx=i+Mp[i];
			id=i;
		}
	}
}
int main()
{
	scanf("%s",s);
	int len=strlen(s);
	Manacher(s,len);
	int ans=0;
	for(int i=0;i<(len<<1)+2;i++) ans=max(ans,Mp[i]-1);
	printf("%d\n",ans);

	return 0;
}

最小表示法

对于长度为n的字符串s,我们把它首尾相连形成一个环，然后再任一位置断开得到的字符串t与s循环同构。
\(t_i=s[i\dots n]+s[1\dots i-1], 1\leqslant i \leqslant n\)
再n个与s循环同构的字符串中,字典序最小的那个称为s的最小表示。

如何求出s的最小表示？

暴力 \(O(n^2)\)

把这n个与s循环同构的字符串求出来,然后选个字典序最小的即可

稍微的优化: 把s复制一遍加到原串后,这时与s循环同构的字符串都是新串长度为n的子串

但两个时间复杂度还都是\(O(n)\)

最小表示法 \(O(n)\)

用两个指针i,j,分别指向到目前为止两个可能是答案串的串的起始位置

初始i=1,j=2,随着算法进行两者逐步增大

假设i<j,且从i开始的k位字符和从j开始k位字符是一样的,此时\(s[i\dots i+k-1]=s[j\dots j+k-1](k\leqslant n)\) 如图所示

如\(s[i+k] \neq s[j+k]\) 我们可以得到那些信息？

  1. 若\(s[i+k] > s[j+k]\) :则i位置显然不可能是最总答案了,i要往后移
    注意\(s[i \dots i+k-1]\)和\(s[j \dots j+k-1]\)完全相等,且\(s[i+k]>s[j+k]\)那么i到i+k都不可能是答案

i可以直接挪到i+k+1的位置,此时i可能会大于等于j,两者相等时我们随便选择一个指针把其向后挪一位

  1. \(s[i+k]<s[j+k]\):此时j不可能是最总答案,j需要往后挪
    j到j+k都不可能是答案，j直接挪到j+k+1的位置
    更新完检查i,j是否相等(实际不存在)

  2. \(s[i+k] == [j+k]\):直接往后挪一个即可

算法会在i,j两个指针中有一个大于n的时候终止
此时仍然在字符串范围内的那个指针指向的位置就是要的答案

算法模板

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=1e5+10;
char s[N<<1],p[N<<1];
string getmin(char x[],int n)
{
	for(int l=0;l<n;l++) x[l+n]=x[l];
	int i=0,j=1;
	while(j<n)
	{
		int k=0;
		while(k<n&&x[i+k]==x[j+k]) k++;
		if(x[i+k]>x[j+k]) i+=k+1;
		else j+=k+1;
		if(i==j) j++;
		if(i>j) swap(i,j);
	}
	string res="";
	for(int l=i;l<=i+n-1;l++) res+=x[l];
	return res;
}
int main()
{
	scanf("%s%s",s,p);	
	if(getmin(s,strlen(s)) == getmin(p,strlen(p))) puts("Yes");
	else puts("No");

	return 0;
}

例题

分析:找到最小表示相等即可

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=1e5+10;
char s[N<<1],p[N<<1];
string getmin(char x[],int n)
{
	for(int l=0;l<n;l++) x[l+n]=x[l];
	int i=0,j=1;
	while(j<n)
	{
		int k=0;
		while(k<n&&x[i+k]==x[j+k]) k++;
		if(x[i+k]>x[j+k]) i+=k+1;
		else j+=k+1;
		if(i==j) j++;
		if(i>j) swap(i,j);
	}
	string res="";
	for(int l=i;l<=i+n-1;l++) res+=x[l];
	return res;
}
int main()
{
	scanf("%s%s",s,p);	
	if(getmin(s,strlen(s)) == getmin(p,strlen(p))) puts("Yes");
	else puts("No");

	return 0;
}

分析:先用kmp求出最小循环覆盖的长度n，然后再取最小表示前n位

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=1e5+10;
char s[N<<1];
int nxt[N],minl;
void pre_KMP(char x[],int m)
{
	int i,j;
	j=nxt[0]=-1;
	i=0;
	while(i<m)
	{
		while(-1!=j&&x[i]!=x[j]) j=nxt[j];
		nxt[++i]=++j;
	}
}
void getmin(char s[],int n)
{
	for(int l=0;l<n;l++) s[l+n]=s[l];
	int i=0,j=1;
	while(j<n)
	{
		int k=0;
		while(k<n&&s[i+k]==s[j+k]) j++;
		if(s[i+k]>s[j+k]) i+=k+1;
		else j+=k+1;
		if(i==j) j++;
		if(i>j) swap(i,j);
	}
	for(int l=i,cnt=0;cnt<minl;cnt++,l++) cout<<s[l];
	cout<<endl;
}
int main()
{
	scanf("%s",s);
	pre_KMP(s,strlen(s));
	minl=strlen(s)-nxt[strlen(s)];
	// cout<<minl<<endl;
	getmin(s,strlen(s));

	return 0;
}