Manacher 马拉车算法计算回文子串

最近开始刷算法题,
在刷第五题的时候,看到一个有意思的算法,总结一下

计算回文子串,首先简单的有

暴力破解法,就是挨个循环,计算每两个字符之间是不是回文子串,如果是和当前保存的最大的回文子串比较
时间复杂度：O(N³),空间复杂度 O(1)

中心扩散 以每个字符为中心,计算回文串的长度,和当前保存的最大的回文子串比较.
时间复杂度:O(N²),空间复杂度O(1);

动态规划 声明一个二维数组,保存两个字符之间是不是回文子串的状态,如果两个字符(i,j)相等,那么 i+1,j-1 是回文子串,则(i,j) 也是回文子串,
注意事项：总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要。
时间复杂度O(N²),空间复杂度O(N²);

Manacher算法

Manacher 算法是基于“中心扩散法”，采用和 kmp 算法类似的思想，依然是“以空间换时间”。
使用了类似 KMP 算法的技巧，充分挖掘了已经进行回文判定的子串的特点，在遍历的过程中，记录了已经遍历过的子串的信息
时间复杂度 O(N), 空间复杂度O(N)

第 1 步：对原始字符串进行预处理（添加分隔符）

首先在字符串的首尾、相邻的字符中插入分隔符，例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。

对这一点有如下说明：

1. 分隔符是一个字符，种类也只有一个，并且这个字符一定不能是原始字符串中出现过的字符；
2. 加入了分隔符以后，使得“间隙”有了具体的位置，方便后续的讨论，并且新字符串中的任意一个回文子串在原始字符串中的一定能找到唯一的一个回文子串与之对应，因此对新字符串的回文子串的研究就能得到原始字符串的回文子串；
3. 新字符串的回文子串的长度一定是奇数；
4. 新字符串的回文子串一定以分隔符作为两边的边界，因此分隔符起到“哨兵”的作用。

  private String addBoundaries(String s, char divide) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        if (s.indexOf(divide) != -1) {
            throw new IllegalArgumentException("参数错误，您传递的分割字符，在输入字符串中存在！");
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            stringBuilder.append(divide);
            stringBuilder.append(s.charAt(i));
        }
        stringBuilder.append(divide);
        return stringBuilder.toString();
    }

第 2 步：计算辅助数组 p

辅助数组 p 记录了新字符串中以每个字符为中心的回文子串的信息。
采取“中心扩散法”，此时记录以当前字符为中心，向左右两边同时扩散，能够扩散的最大步数。

image.png

第3步:更有效率的计算辅助数组p

需要一些辅助变量,
maxRight计算回文子串到字符串最右边的值.
center 和 maxRight 相关联的回文子串的中心
' mirror ' mirror 和 i 关于center对称, (i+mirror) /2 == center ,
可以通过 p[mirror] 计算出 p[i]的大致值.再进行中心扩散算法,如果 i+p[i] 超过了 maxRight,则center = i, maxRight = i+p[i];

  public String longestPalindrome(String s) {

        if (s.length()<2){
            return s;
        }

        String str = addBoundaries(s,'#');

        int strLen = str.length();

        // 数组 p 记录了扫描过的回文子串的信息
        int []p = new int[strLen];

        // 原始字符串的最长回文子串的起始位置，与 maxLen 必须同时更新
        int start = 0;
        // 当前遍历的中心最大扩散步数，其值等于原始字符串的最长回文子串的长度
        int maxLen = 0;

        // 双指针，它们是一一对应的，须同时更新
        int center = 0;
        int maxRight = 0;

        for (int i = 0; i<strLen; i++){
            if (i < maxRight){
                int mirror = 2*center - i;
                // 只是大概值,如果i+p[i] >= maxRight那么还需要中心扩散
                p[i] = Math.min(p[mirror], maxRight - i);
            }
            int left = i - p[i] -1;
            int right = i + p[i] + 1;
            // 中心扩散算法
            while((left >=0) && (right<str.length()) && (str.charAt(right) == str.charAt(left))){
                left--;
                right++;
                p[i]++;
            }

            // 更新center和maxright的值
            if (i + p[i]>maxRight){
                center = i;
                maxRight = i+p[i];
            }
            if (p[i] > maxLen){
                maxLen = p[i];
                start = (i - p[i])/2;// 除以2 是要计算原始子串的位置
            }
        }
        return s.substring(start,start+maxLen);
    }

参考链接
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/