最长回文子串

发表于 更新于 分类于 阅读次数：

最长回文子串是字符串处理中最经典的问题之一，其解决方法有多种，效率也不一样。下面分别介绍几种解决方法。

0x01. 动态规划

时间复杂度：o(n^2), 空间复杂度：o(n^2).
动态规划方程：

1
2
3
4
5
dp[i][j] 表示子串s[i…j]是否是回文
初始化：
   dp[i][i] = true (0 <= i <= n-1);
   dp[i][i-1] = true (1 <= i <= n-1); 其余的初始化为false
dp[i][j] = (s[i] == s[j] && dp[i+1][j-1] == true)

0x02. Manecher算法

时间复杂度：o(n), 空间复杂度：o(n).
该算法首先对字符串进行预处理，在字符串的每个字符前后都加入一个特殊符号，比如字符串 abcb 处理成#a#b#c#b#。为了避免处理越界，在字符串首尾加上不同的两个特殊字符（C类型的字符串后面有’\0’，不用加），最后预处理的字符串为^#a#b#c#b#。
就以上面的字符串为例，经过预处理后，变成s= “^#a#b#c#b#”;
设数组p[i]的值为以字符s[i]为中心的最长回文子串向两边扩展的长度（包括s[i]）,以上述字符串为例：

1
2
3
s:  ^ # a # b # c # b #
p:    1 2 1 2 1 4 1 2 1

仔细观察可以发现，p[i]-1 正好是原字符串中回文串的总长度。
p[]数组的求法：
设id是当前求得的最长回文子串中心的位置，mx是当前最长回文子串的右边界（回文子串不包括该右边界），即mx = id + p[id]。设i是id右边的位置，则关于id对称的点j = id-(i-id)= 2*id-i。

  1. 当 mx > i 时：
    如果 mx-i > p[j], 则以s[j]为中心的回文子串包含在以s[id]为中心的回文子串中。由于i和j对称，那么以s[i]为中心的回文子串必然包含在以s[id]为中心的回文子串中。所以至少 p[i]>=p[j]，后面的在继续匹配。
    如果 mx-i <= p[j], 则以s[j]为中心的回文子串不完全包含于以s[id]为中心的回文子串中。但由于对称性，以s[i]为中心的回文串，其向右至少会扩展到mx的位置，即p[i]至少等于 mx-i,至于后面的部分是否对称，只好一一匹配。
  2. 当 mx <= i 时：
    无法对p[i]做更多的假设，只能p[i] = 1, 然后再去匹配。
    上述过程的C语言实现如下： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //输入预处理的字符串s
    int p[MAXN], mx = 0, id = 0;
    memset(p, 0, sizeof(p));
    for (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;
        }
    }
    //找出p[i]中最大的

0x03. 后缀数组（后缀树）

待续。。。