最长回文子串 ( manacher算法 ) HDU3068

给出一个字符串，要求最长的回文子串。回文的意思是字符串关于中心对称。

为了解决这个问题，一般的思维是向两侧扩展的枚举中心。它还分为奇偶和偶数长度的子串。这种解决方案的时间复杂性是O(n^2)，对于较长的字符串，仍然不能接受。manacher算法提供了时间复杂性(n)解决方案。

在【介绍】中提到的枚举中心的方法，加上一些优化，就能达到manacher的目的。 1、为了方便起见，我们先处理奇偶长度的问题。

我们在给定字符串的所有间隙中插入一个从未出现过的字符，不妨使用“#”

例如，“ab”变为“#a#b#”，“aba”变为“#a#b#a#”。

巧妙地转化为奇数长度了吗？

转换后的字符串为s

2、用数组p[i]当记录以第一个字符为中心时，最多可以向两侧扩展多久。只有中心对称才能扩展。

s[i]

#

a

#

b

#

a

#

p[i]

1

2

1

4

1

2

1

假设现在是s[i]计算p[i]值，用变量id记录i前右边界最大的下标。也就是说，s[id]对称回文串的右边界最大。看起来和暴力一样。暴力会反复访问一些子串，我们可以避免这样的事情。添加辅助变量id

for(int i=0;i<strlen(s);i++){

第一步是用发现的回文串信息给当前位置i一个可能的最大p[i]值。

考虑到目前的i位置，在找不到的最长回文串内部，即 i < id+p[id]。

若i < id+p[id]，则p[i]=p[id*2-i](i关于id对称的位置)，否则，让p[i]=1;

第二步，根据已获得的p[i]值，继续向两侧扩展，以获得p[i]正确的最大值。

第三步，更新id值

}

3、对于计算完成的p数组，找到ans记录的最大值，ans-1是最长回文子串的长度，可以自行验证。

[例题HDU3068]https://www.tulingxueyuan.cn/d/file/p/20230529/z0yqgsoyfqf.图灵 class='language-plain'>#include<bits/stdc++.h>using namespace std;const int MAX=221000;char str[MAX];///原始字符串charar s[MAX*2];///插空串int p[MAX*2];///上述数组的下标均从0开始 manacher(){ int n=strlen(str)*2+1;///插空串长度 int id=0; ////最长回文串的中心 s[0]=###; for(int i=0,j=1;str[i];i++) { s[j++]=str[i]; s[j++]='#'; } int ans=0; p[0]=1;//初始 for(int i=1;i<n;i++)//对p[i]计算 { if(i < id+p[id])///i包含在最大回文串中 p[i]=min(p[id*2-i],id+p[id]-i);//对称点的p值，否则i到p[id]右边界的距离 else p[i]=1; while(i-p[i]>=0&&s[i-p[i]]==s[i+p[i]])p[i]++;//往外扩 if(id+p[id]<i+p[i])id=i;//比较右边界 if(ans<p[i])ans=p[i]; } return ans-1;}int main(){ while(~scanf("%s",str)) printf("%d\n",manacher());}