manacher算法求最长回文子串

发表于   |   分类于

最长回文子串

题目

给定一个字符串，求它的最长回文子串的长度。

分析与解法

最容易想到的办法是枚举所有的子串，分别判断其是否为回文。这个思路初看起来是正确的，但却做了很多无用功，如果一个长的子串包含另一个短一些的子串，那么对子串的回文判断其实是不需要的

解法一

那么如何高效的进行判断呢？我们想想，如果一段字符串是回文，那么以某个字符为中心的前缀和后缀都是相同的，例如以一段回文串”aba”为例，以b为中心，它的前缀和后缀都是相同的，都是a。由此可见，我们可以枚举中心位置，然后再在该位置上用扩展法，记录并更新得到的最长的回文长度

枚举中心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int palindrome(char s[])
{
    int len=strlen(s);
    int ans=0;
    for(int i=0;i<len;i++){
        int l=i,r=i;     //回文串长度为奇数
        while(l>=0&&r<len&&s[l]==s[r]){
            ans=max(ans,r-l+1);
            l--,r++;
        }
        l=i,r=i+1;      //回文串长度为偶数
        while(l>=0&&r<len&&s[l]==s[r]){
            ans=max(ans,r-l+1);
            l--,r++;
        }
    }
    return ans;
}

解法二：O(N)解法

在上文的解法一：枚举中心位置中，我们需要特别考虑字符串的长度是奇数还是偶数，所以导致我们在编写代码实现的时候要把奇数和偶数的情况分开编写，是否有一种方法，可以不用管长度是奇数还是偶数，而统一处理呢？比如是否能把所有的情况全部转换为奇数处理？
答案还是肯定的。这就是下面我们将要看到的Manacher算法，且这个算法求最长回文子串的时间复杂度是线性O(N)的。
首先通过在每个字符的两边都插入一个特殊的符号，将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。

此外，为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符(最后也有特殊字符空字符)，这样就不用特殊处理越界问题，比如$#a#b#a#。

以字符串12212321为例，插入#和$这两个特殊符号，变成了 S[] = “$#1#2#2#1#2#3#2#1#”，然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左或向右扩张的长度（包括S[i]）。
比如S和P的对应关系：

  • S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
  • P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
    可以看出，P[i]-1正好是原字符串中最长回文串的总长度，为5。
    关键是怎么计算P[i],Manacher算法增加两个辅助变量id和mx，mx=max(k+P[k]) (k>=0&&k i，那么P[i] >= Min(P[2 * id - i], mx - i)
    1
    2
    3
    4
    5
    6
    //mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)
    //故谁小取谁
    if (mx - i > P[2*id - i])
        P[i] = P[2*id - i];
    else  //mx-i <= P[2*id - i]
        P[i] = mx - i;

下面，令j = 2*id - i，也就是说j是i关于id的对称点。
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于i和j对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有P[i] = P[j]；
manacher
当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，再具体匹配。
manacher
此外，对于 mx <= i 的情况，因为无法对 P[i]做更多的假设，只能让P[i] = 1，然后再去匹配。

Manacher算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int manacher()
{
    int id=0,mx=0,maxlen=0;
    p[0]=0;
    for(int i=1;s[i]!='\0';i++){
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(s[i+p[i]]==s[i-p[i]])
            p[i]++;
        if(i+p[i]>mx){
            mx=i+p[i];
            id=i;
        }
        if(p[i]>maxlen)  //求最大回文长度
            maxlen=p[i];
    }
    return maxlen-1;
}

Hdu 3068 最长回文

链接

最长回文

参考代码

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=240000;
char s[N],t[N];
int p[N];
int manacher()
{
    int len=strlen(t);
    for(int i=0;i<=len;i++){
        s[i*2+1]='#';
        s[i*2+2]=t[i];
    }
    s[0]='$';
    p[0]=0;
    int id=0,mx=0,maxlen=0;
    for(int i=1;i<=2*len;i++){
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(s[i+p[i]]==s[i-p[i]])
            p[i]++;
        if(i+p[i]>mx){
            mx=i+p[i];
            id=i;
        }
        if(p[i]>maxlen)
            maxlen=p[i];
    }
    return maxlen-1;
}
int main()
{
    while(scanf("%s",t)!=EOF){
        int ans=manacher();
        printf("%d\n",ans);
    }
    return 0;
}