12/23

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;
}