1089 最长回文子串V2 (Manacher算法)
描述
题解
回文分为偶回文和奇回文,在处理就问题上比较繁琐,所以这里使用一个技巧,具体做法是:在字符串首尾及各字符间各插入一个字符(该字符从未在串中出现)。
例如:s='daabaacabba'
,转化为s_new='$#d#a#a#b#a#a#c#a#b#b#a#'
,上述的s
中起初有一个奇回文aadaa
和一个偶回文abba
,被转化为#a#a#d#a#a#
和#a#b#b#a#
,长度都转化成奇数了。
一、Manacher
定义数组dp[]
,dp[i]
表示以i
为中心的最长回文的半径。以上述的s=daabaacabba
为例:
接下来重点是求解数组dp[],
考虑dp[i],
i<p,由上图可知,以P0为中心的i的对称坐标为j=2*P0-i,
1)若dp[j]<=p-i,由回文串的对称性可知,dp[i]=dp[j],
2)若dp[j]>p-i,则未超出的部分可以作为初始值,超出的部分则需要进行一一计算了。
每计算完一次dp[i],都需要重新更新一下P0以及p
代码
#include<cstring>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define maxn 100000
using namespace std;
char s[maxn];
char s_new[2*maxn];
int dp[2*maxn];
int Init(){
int len=strlen(s);
s_new[0]='$';///新填充的字符串的首字符
s_new[1]='#';
int j=1;
for(int i=0; i<len; i++){
s_new[++j]=s[i];
s_new[++j]='#';
}
s_new[++j]='\0';///新填充的字符串的尾字符
return j;///返回s_new的长度
}
int manacher(){
int len=Init();
int max_len=-1;///最长回文长度
int mx=0,idx;
for(int i=1; i<len; i++){
if(i<mx){
dp[i]=min(dp[2*idx-i],mx-i);
}
else{
dp[i]=1;
}
///这里无需进行越界判断,因为初始化时,首尾字符已经不同了
/// i-dp[i]与i+dp[i]关于i对称(i-dp[i]+i+dp[i])/2=i
while(s_new[i-dp[i]]==s_new[i+dp[i]])
dp[i]++;
///更新mx,idx 注意max_len的更新方式。
if(mx<i+dp[i]){
idx=i;
mx=i+dp[i];
}
max_len=max(max_len,dp[i]-1);
}
return max_len;
}
int main()
{
while(scanf("%s",s)==1)
{
printf("%d\n",manacher());
}
return 0;
}