最长回文子串

给一个字符串,求最长的回文子串。女朋友说Manacher看不懂,我专门写了图形演示的程序。她看了之后,一会儿就ac了。

暴力解法

遍历字符串,每次以一个位置为中心(字符或两个字符),向两边扩展,这样的解法时间复杂度是O(n*n)。

Manacher算法

单纯暴力的方法,没有利用一个有效的信息,就是在当前扩展中心位置i之前的位置,我们已经求出了它们为中心的最长回文串,并且在某个长回文串中,我们有可能找到关于这个回文串中心轴对称的点。

首先,算法的大致框架和暴力解法相同,枚举字符串的每一个字符,从左到右,对于每一个字符,向两边扩展,求出以该点为中心的最大的回文子串。

在这个过程中,我们要维护以下的数据结构:

ext[],这个数组的大小和母串长度相同,ext[i]代表从i位置向两方扩展的长度,举例,abc的话,ext[1]=1;aba的话,ext[1]=2

mid,向右扩展能够达到最右的回文子串的中心下标。

max_mid,整个算法过程中,最长回文子串的中心下标。

在开始算法前,要完成一个预处理。因为回文子串有两种,偶数长和奇数长,分情况处理起来比较麻烦。我们把原串的中间和两侧都插入一个不会在串中存在的字符,开头再加另外一个不会出现的字符,结尾加\0。例如,aba变成了^#a#b#a#,abba变成了^#a#b#b#a#。这样处理的好处,无论原串的奇偶,都处理成了奇数,只有一种情况,而且还不影响原来的结果,开头加一个唯一的字符,是为了少判断个数组越界。

好了,想好了数据结构,做好了预处理,就可以开始算法了,即在算法的大致框架中维护这些数据结构。

对于当前的遍历到的位置i,我们准备向两边扩展得到以它为中心的最长回文子串了,在这个干之前,我们看看有啥可以利用的。我们已经知道mid是已知向右最远回文子串的中心下标,那么这个回文串最远覆盖的位置就是mid+ext[mid]-1,如果mid+ext[mid]>i,这样的情况出现,先窃喜一下,因为我们可以知道i关于mid对称的位置mid2-i的情况ext[mid2-i],想象一下,以mid2-i为中心的最长回文子串被以mid为中心的回文子串完全覆盖,是不是ext[i]=ext[mid2-i]了啊。但是如果超出里mid回文的范围,ext[i]至少可以扩展到mid回文的边界,也就是ext[i]=ext[mid]+mid-i(好好算下下标)。

好了,ext[i]根据上面的有效信息,已经得到一个不错的开始,倘若i就在mid回文之外呢,我靠,那就ext[i]=1开始呗。无论如何,这一步都要接着像暴力那样扩展。

扩展结束了,维护一波mid,维护一波max_mid。

演示程序

这有一个演示程序,蓝色代表当前的回文扩展,绿色代表最右覆盖的回文,红色代表最长的回文。

给一个字符串,求最长的回文子串。女朋友说Manacher看不懂,我专门写了图形演示的程序。她看了之后,一会儿就ac了。

暴力解法

遍历字符串,每次以一个位置为中心(字符或两个字符),向两边扩展,这样的解法时间复杂度是O(n*n)。

Manacher算法

单纯暴力的方法,没有利用一个有效的信息,就是在当前扩展中心位置i之前的位置,我们已经求出了它们为中心的最长回文串,并且在某个长回文串中,我们有可能找到关于这个回文串中心轴对称的点。

首先,算法的大致框架和暴力解法相同,枚举字符串的每一个字符,从左到右,对于每一个字符,向两边扩展,求出以该点为中心的最大的回文子串。

在这个过程中,我们要维护以下的数据结构:

ext[],这个数组的大小和母串长度相同,ext[i]代表从i位置向两方扩展的长度,举例,abc的话,ext[1]=1;aba的话,ext[1]=2

mid,向右扩展能够达到最右的回文子串的中心下标。

max_mid,整个算法过程中,最长回文子串的中心下标。

在开始算法前,要完成一个预处理。因为回文子串有两种,偶数长和奇数长,分情况处理起来比较麻烦。我们把原串的中间和两侧都插入一个不会在串中存在的字符,开头再加另外一个不会出现的字符,结尾加\0。例如,aba变成了^#a#b#a#,abba变成了^#a#b#b#a#。这样处理的好处,无论原串的奇偶,都处理成了奇数,只有一种情况,而且还不影响原来的结果,开头加一个唯一的字符,是为了少判断个数组越界。

好了,想好了数据结构,做好了预处理,就可以开始算法了,即在算法的大致框架中维护这些数据结构。

对于当前的遍历到的位置i,我们准备向两边扩展得到以它为中心的最长回文子串了,在这个干之前,我们看看有啥可以利用的。我们已经知道mid是已知向右最远回文子串的中心下标,那么这个回文串最远覆盖的位置就是mid+ext[mid]-1,如果mid+ext[mid]>i,这样的情况出现,先窃喜一下,因为我们可以知道i关于mid对称的位置mid2-i的情况ext[mid2-i],想象一下,以mid2-i为中心的最长回文子串被以mid为中心的回文子串完全覆盖,是不是ext[i]=ext[mid2-i]了啊。但是如果超出里mid回文的范围,ext[i]至少可以扩展到mid回文的边界,也就是ext[i]=ext[mid]+mid-i(好好算下下标)。

好了,ext[i]根据上面的有效信息,已经得到一个不错的开始,倘若i就在mid回文之外呢,我靠,那就ext[i]=1开始呗。无论如何,这一步都要接着像暴力那样扩展。

扩展结束了,维护一波mid,维护一波max_mid。

演示程序

这有一个演示程序,蓝色代表当前的回文扩展,绿色代表最右覆盖的回文,红色代表最长的回文。




Your browser does not support the HTML5 canvas tag.

代码

https://leetcode.com/problems/longest-palindromic-substring/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int min(int a,int b){
return a<b?a:b;
}
char* longestPalindrome(char* s) {
char* ans = (char*)malloc(1005*sizeof(char));
char* ss = (char*)malloc(2010*sizeof(char));
int* ext = (int*)malloc(2010*sizeof(int));
int len = strlen(s);
int i,j,mid,max_mid;
for(i=0;i<len;i++){
ss[i+i+1] = 1;
ss[i+i+2] = s[i];
}
ss[0]=2;ss[(len<<1)+1]=1;ss[(len<<2)+2]=0;
mid=max_mid=0;
ext[0]=0;
for(i=2;i<(len<<1|1);i++){
if(ext[mid]+mid>i)ext[i]=min(ext[mid]+mid-i,ext[(mid<<1)-i]);
else ext[i]=1;
while(ss[i-ext[i]]==ss[i+ext[i]])ext[i]++;
if(ext[i]+i>ext[mid]+mid)mid=i;
if(ext[i]>ext[max_mid])max_mid=i;
}
int cnt=0;
for(i=max_mid-ext[max_mid]+1;i<max_mid+ext[max_mid];i++){
if(ss[i]!=1&&ss[i]!=2)ans[cnt++]=ss[i];
}
ans[cnt]=0;
return ans;
}
int main(){
char s[10000];
scanf("%s",s);
printf("%s\n",longestPalindrome(s));
return 0;
}