Manachar算法(马拉车算法)：快速求取最长回文子串

当我们求取最长回文子串时，常见的方法就是中心扩散法，即从字符中心出发，向两边对比，检查是否相等，若等于，则继续检查，并使当前字符中心对应的最长回文子串长度加一，否则，结束该字符中心的回文检查，比较与当前整个字符串的最长回文子串，考虑是否更新整个字符串的最长回文子串长度，继续进行下一个字符的判断。

这种方法的时间复杂度仍为 $O(n^2)$ ，较普通的暴力破解的方法有着不错的优化，但也不是最佳的思路，相关的代码如下：

public class Solution {
    private int max = 0;
    private String res = "";
    public String longestPalindrome(String s) {
        if (s.length() == 1) { return s; }
        for (int i = 0; i < s.length()-1; i++) {
            checkPalindromeExpand(s,i,i);
            checkPalindromeExpand(s,i,i+1);
        }
        return res;
    }
    public void checkPalindromeExpand(String s, int low, int high) {
        while (low >= 0 && high < s.length()) {
            if (s.charAt(low) == s.charAt(high)) {
                if (high - low + 1 > max) {
                    max = high - low + 1;
                    res = s.substring(low,high+1);
                }
                low--; high++;
            } else {
                return;
            }
        }
    }
}
复制代码

当然，上面这种算法也有优化的空间，基本的思路如下：

• 统计字符出现频率，用数组表示出现频率，当某个字符出现频率为 1 时，认为该字符可能为某段回文子串的中心点，否则，就不属于任何一个回文子串
• 找出频度为1的字符a，看以a为单核中心向外扩散，求最长回文；如果没有回文，就将它从串中断开，进行分治；如果回文长度超过记录，就保存它
• 然后从左到右查回文，只有长度超过记录，才保存
• 第一次串分割完毕后，进行分治，重新统计频度，回到1步骤

实现代码可以借鉴：小马哥最长回文子串长度求取

Manachar算法

求取最长回文子串的长度的最佳方法为 Manachar算法 ，俗称马拉车算法。在了解这个算法之前，我们必须先理解回文子串的一些性质：

• 假设对于一个回文串，以及其中心位置，由回文串的性质可知，从其中心向两侧逐步扩散到边界为止，每一步所对应范围的字串都是回文串

• 如果我们已知一个回文串的中心点 mid 与其边界范围。那么，在大多数情况下，位于边界内且关于此中心点对称的两点a、b，如果有回文串以 a 为中心，那么以 b 为中心的回文串与以 a 为中心的回文串完全相同。并且，它们之间存在这样的关系：$b = 2 \times mid – a$

• 回文串末尾位置到回文串中心位置的字符长度为该回文串的半径，若末尾位置的下标为 a ，中心位置的下标为 id ，回文串长度半径为 len ，即半径为 len 则它们存在如下关系：

  $$a = id + len\div2$$

  © 版权声明

  文章版权归作者所有，未经允许请勿转载。
  THE END
  后端