Manacher算法

前言

Manacher算法用于求解字符串中最长的回文子串，它和KMP算法的改进方式很类似，都是基于暴力求解的方法，通过利用历史信息进行优化。所谓回文子串是指以子串中间字符为中心，左右两端是对称的。例如,cbcacb的最长回文子串为bcacb，其长度为5。
相关题目：5. 最长回文子串

最长回文子串的暴力求解

• 遍历字符串中的每个字符，比较其左右关于该字符为中心对称的位置的字符是否相同，如果相同比较该字符的左边的左边和右边的右边字符是否相同，以这种向外“扩”的方式计算以每个字符为中心的回文子串长度。

  
  
  

  暴力求解的时间复杂度是O(n * n)

Manacher算法

Manacher算法基于暴力求解做出优化，它定义了如下几个概念：

• 回文半径：以某个字符为中心向外扩的字符个数称为字符的回文直径，那么回文半径不言而喻。例如cbcacb，以字符a为中心向外扩，可以扩c，再扩b，再加上字符本身，字符a的回文半径是3。
• 回文半径数组pArr：记录以每个字符为中心的回文半径。例如上图的回文半径数组为[1,2,1,3,1,1].
• 最右回文右边界R：向外扩的过程中，扩到的最右字符的下标。例如字符串cbcacb，遍历到第一个c，其只能扩到自己，则R = 0；遍历到b时，可以扩一个c，则R = 2.（一旦能扩到更右的字符，必须更新R）
• 最右回文右边界对应的回文中心C：C和R是对应的，R正是中心C所能扩到的最右字符下标，因此R和C是同时更新的。

我们的“扩”是基于一个中心向外扩的，扩出来的回文子串长度必是奇数。为了处理回文子串为偶数的情况，我们在字符间插入一个字符#以保证回文子串长度都是奇数。例如，字符串cbcacb - > #c#b#c#a#c#b#。

Manacher算法如何利用pArr、C和R对查找进行加速

我们以指针cur去遍历字符串，

• 情况1：
  当cur位于R的右边时，这种情况无法使用回文半径数组pArr进行加速，只能暴力向外扩。
• 情况2：
  当cur位于R的左边时，此时可以利用回文半径数组pArr来进行加速处理。
  首先，画出R、cur关于中心C的对称点，
  • 如果以cur'为中心的回文子串的左边界没有超出L(也没有压线)，如下图
    
    那么，pArr[cur] = pArr[cur']。
    证明：首先，L -> C和C -> R这两块是对称的，身为子块的x' -> y'的对称块为y -> x，所以pArr[cur] = pArr[cur']。
    疑问：pArr[cur]有没有可能比pArr[cur']大？不可能，假设y前面的一个字符 == x后面的一个字符，那当时扩cur'时，为什么不扩，它们是对称的。
  • 如果以cur'为中心的回文子串的左边界超出了L，如下图
    
    那么，pArr[cur] = R - cur + 1。
    证明：假设R的右边一个字符为x，它的对称字符为x'，根据pArr[C]，x' != x；又x' == y'，y' == y，推出x != y。因此，以cur为中心的回文半径为R - cur + 1。
  • 如果以cur'为中心的回文子串的左边界刚好压中L，如下图
    
    这种情况下，y的前一个字符和x的后一个字符的关系无法通过历史信息推算出来，只知道以cur为中心的回文子串半径至少为R - cur + 1，因此需要继续向外扩以确定pArr[cur]。

综上所述，分四种情况：

• cur在R右边，暴力扩
• cur在R左边
  • cur'回文左边界没超过L，pArr[cur] = pArr[cur']
  • cur'回文左边界超出L，pArr[cur] = R - cur + 1
  • cur'回文左边界压中L，pArr[cur] = R - cur + 1 + 继续向外扩

时间复杂度

• 遍历了一遍字符串，O(n)

相关题目

最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;
        char[] m = manacherString(s);
        int[] pArr = new int[m.length];
        int c = -1;
        int r = -1;
        int maxLen = -1;
        StringBuilder maxStr = new StringBuilder();
        for(int i = 0;i != m.length;i++){
            //i在r右边，直接1；否则就是pArr[cur']或R - cur + 1
            pArr[i] = i < r ? Math.min(pArr[2 * c - i], r - i + 1) : 1;
            //看能不能扩(针对压中L和暴力扩的情况)
            while(i - pArr[i] >= 0 && i + pArr[i] < m.length
                  && m[i - pArr[i]] == m[i + pArr[i]]){
                pArr[i]++;
            }
            if(i + pArr[i]- 1 > r){
                c = i;
                r = i + pArr[i] - 1;
            }
            if(maxLen <= pArr[i]){
                maxLen = pArr[i];
                maxStr.delete(0,maxStr.length());
                for(int j = i - pArr[i]+1;j < r;j++){
                    if(m[j] != '#'){
                        maxStr.append(m[j]);
                    }
                }
            }
        }
        return maxStr.toString();
    }
    private char[] manacherString(String s){
        char[] m = new char[2 * s.length() + 1];
        for(int i = 0;i < m.length;i++){
            m[i] = i % 2 == 0? '#' : s.charAt(i / 2);
        }
        return m;
    }
}