526互联

12/23

发布时间 2023-12-23 17:31:57作者: 某不知名碳基生物

manacher

核心

  • 在 O(n)的时间内，求出一个长度为n的字符串的最长回文子串
  • 过程
  1. 预处理：将 abbacd 变 #a#b#b#a#c#d# 避免偶回文没有回文中心
  2. 中心扩展：枚举每个回文中心位置i，看最多能向两边扩展多少　　
  • 将以每个i为回文中心的最大回文半径记为pi
  • 记录x,使得以x为回文中心扩展出去的回文串的右端点最大,记录最右端点R,最左端L　

    • 现在算 pi 有两种情况：

      1. i>R    暴力向两侧扩展
      1. i<=R    进行优化

　　　　　　　　因为p;在回文串[L,R]内，所以必有一个和它相同的位置 &nbsp;<span class="math inline">j=x&lt;&lt;1&minus;i，它 它们关于x对称

　　　　　　　　由于&nbsp;<span class="math inline">j&lt;i，那么它的&nbsp;<span class="math inline">pj&nbsp;已经计算了

    • 如果以 j&nbsp;为回文中心的回文串不包含&nbsp;<span class="math inline">L<span class="math inline">，那么&nbsp;<span class="math inline">i&nbsp;肯定也扩展不了了。比较j与L的长度和i与R的长度，取较小值，令&nbsp;<span class="math inline">pi=min(pj,R-i+1)

    • 如果以 j&nbsp;为回文中心的回文串包含&nbsp;<span class="math inline">L<span class="math inline">，那么从&nbsp;<span class="math inline">L&nbsp;再向外的那一节&nbsp;<span class="math inline">i&nbsp;就不能适用了。令&nbsp;<span class="math inline">pi=R&minus;i+1&nbsp;后，从&nbsp;<span class="math inline">R&nbsp;开始进行暴力扩展

 

 

模板代码 

 

#include <bits/stdc++.h>
using namespace std;
const int N =1.1e7+5;
int ans,n,len;
int R,x; 
int p[N<<1]; 
char s[N],st[N<<1];

int main()
{
	cin>>(s+1);
	len=strlen(s+1);//从1开始
	st[++n]='#';
	for(int i=1;i<=len;i++) 
	{
		st[++n]=s[i];
		st[++n]='#';
	}//预处理 st为新处理后的序列 
		
	for(int i=1;i<=n;i++)
	{
		if(i>R) 
			p[i]=1;
		else
			p[i]=min(R-i+1,p[(x<<1)-i]); 
		while(i-p[i]>=1&&i+p[i]<=n&&st[i-p[i]]==st[i+p[i]]) 
			p[i]++;//暴力扩展 
		if(i+p[i]-1>R) 
			R=i+p[i]-1,x=i;
		ans=max(ans,p[i]);
	}
	printf("%d",ans-1);
	return 0;
}