马拉车算法（Manacher）

概述：

马拉车算法主要用于解决最长回文串的问题，也可以用于求所有回文子串的数量

计算字符串的最长回文字串的朴素算法：

枚举回文串的中点，并且分为两种情况:

一种是回文串长度是奇数的情况
另一种是回文串长度是偶数的情况

时间复杂度为O(n²)

马拉车算法是快速求长度为奇数的回文串的方法。
可以通过转化可以将长度为偶数的回文串转化为奇数长度。

优势：

不用考虑字符串是单数还是双数
时间复杂度为O(n)

算法实现

1.改造字符串

解决字符串单数与双数问题

因为单数的回文串最中间的位置是字符，双数的回文串是中间两个字符中间的位置。为了不考虑字符串是单数还是双数，要对原字符串进行预处理。

改造字符串

在原字符串的每个相邻两个字符中间插入一个分隔符，
在首尾也要添加一个分隔符

分隔符的要求不在原串中出现，一般情况下可以用#号。

此时：

新串的长度 = 源字符串的长度 × 2 + 1，一定为奇数

并且：

通过匹配得到新的字符串的最大回文串的半径R也能得到旧的回文串长度len： len=R-1

证明：

首先在转换得到的字符串中，所有的回文串的长度都是奇数。
那么对于以T[i]为中心的回文串，长度就是2 len[i] - 1。
经过观察可得：回文串中的分隔符一定比其他字符数量多1，也就是由 len[i] 个分隔符，剩下的 len[i] - 1 个字符来自原字符串，所以原串的长度就是 len[i] - 1

例如：

2.创建数组，存储回文子串的回文半径

回文中心C和以C为回文中心的回文串的右边界R（最右边界位置的右一位）初始化为-1，创建半径数组len

3.开始从下标 i = 0去遍历字符串S

核心代码：

len[i] = (R > i) ? Math.min(len[2 * C - i], R - i) : 1;

其中len[2 * C - i]是i以C为中心的对称点的回文半径，R-i是i距离右边界的距离（取最小确保len[i]不会超过当前已知的回文串范围R）

分析：

情况1：i > R ，也就是i在R外，此时没有什么花里胡哨的方法，直接暴力匹配，此时记得看看C和R要不要更新。

情况2：i <= R，也就是i在R内，此时分三种情况，在讨论这三个情况前，我们先构建一个模型

L是当前R关于C的对称点，i'是i关于C的对称点，可知 i' = 2*C - i，并且我们会发现，i'的回文区域是我们已经求过的，从这里我们就可以开始判断是不是可以进行加速处理了

i'的回文区域在L-R的内部，此时i的回文直径与 i' 相同

红线部分是 i' 的回文区域，因为整个L-R就是一个回文串，回文中心是C，所以i形成的回文区域和i'形成的回文区域是关于C对称的。

i'的回文区域左边界超过了L，此时i的回文半径则是i到R

首先我们设L点关于i'对称的点为L'，R点关于i点对称的点为R'，L的前一个字符为x，L'一个字符为y，k和z同理，此时我们知道L - L'是i'回文区域内的一段回文串，故可知R'- R也是回文串。所以我们得到了一系列关系，x = y，y = k，x != z，所以 k != z。这样就可以验证出i点的回文半径是i - R。

i' 的回文区域左边界恰好和L重合，此时i的回文半径最少是i到R，回文区域从R继续向外部匹配

因为 i' 的回文左边界和L重合，所以已知的i的回文半径就和i'的一样了，我们设i的回文区域右边界的下一个字符是y，i的回文区域左边界的上一个字符是x，现在我们只需要从x和y的位置开始暴力匹配，看是否能把i的回文区域扩大即可

总体代码：

public static char[] manacherString(String str) {
    char[] charArr = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    res[0] = '#';
    for(int i = 1; i < res.length; i++){
        if(i % 2 == 0){
            res[i] = '#';
        }
        else{
            res[i] = charArr[(i - 1) / 2];
        }
    }
    System.out.println(res);
    return res;
}

public static int maxLcpsLength(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }
    char[] charArr = manacherString(str);
    //回文半径数组
    int[] len = new int[charArr.length];
    //回文中心点
    int C = -1;
    //以C为中心的右边界
    int R = -1;
    //最长回文半径
    int max = Integer.MIN_VALUE;
    //遍历字符串
    for (int i = 0; i != charArr.length; i++) {
        //第一步直接取得可能的最短的回文半径
        //如果i在回文串内，i的半径等于，右边界到i的距离和i关于R对称点的回文半径的最小值
        //如果i在回文串外：暴力枚举，先置为1（单个字符也是回文串）
        len[i] = R > i ? Math.min(len[2 * C - i], R - i) : 1;
        //当以i为中心的回文串的右边界小于转化后端字符串的右边界（回文串没越界），并且左边界没有越界
        while (i + len[i] < charArr.length && i - len[i] > -1) {
            //取最小值后开始从边界暴力匹配，匹配失败就直接退出
            if (charArr[i + len[i]] == charArr[i - len[i]])
                len[i]++;
            else {
                break;
            }
        }
        //如果以i为中心的右边界的长度，比之前的R大
        if (i + len[i] > R) {
            //更新R为i的右边界
            R = i + len[i];
            //中心点为i
            C = i;
        }
        //跟新最大回文半径
        max = Math.max(max, len[i]);
    }
    return max - 1;
}


public static void main(String[] args) {
    String str1 = "abc123321cba";
    System.out.println(maxLcpsLength(str1));
}

相关题目

最长回文子串

public String longestPalindrome(String s) {

    char[] init = init(s);
    int C = -1;
    int R = -1;
    int max = -1;
    int left = 0;
    int right = 0;
    int[] len = new int[init.length];
    for(int i = 0; i < init.length; i++){
        len[i] = (R > i) ? Math.min(len[2 * C - i], R - i) : 1;
        while(len[i] + i < init.length && i - len[i] > -1){
            if(init[len[i] + i] == init[i - len[i]]){
                len[i] += 1;
            }
            else{
                break;
            }
        }
        if(len[i] + i > R){
            C = i;
            R = len[i] + i;
        }
        if(len[i] > max){
            max = len[i];
            left = (i - len[i] + 1) / 2;
            right = (i + len[i] - 1) / 2;
        }
    }
    return s.substring(left, right);
}

public char[] init(String string){
    char[] charArray = string.toCharArray();
    char[] newCharArray = new char[charArray.length * 2 + 1];
    newCharArray[0] = '#';
    for(int i = 1; i < newCharArray.length; i++){
        if(i % 2 == 0){
            newCharArray[i] = '#';
        }else {
            newCharArray[i] = charArray[(i - 1) / 2];
        }
    }
    return newCharArray;
}

回文子串

public int countSubstrings(String s) {
    if(s == null ||s.length() == 0){
        return 0;
    }
    char[] init = init(s);
    int C = -1;
    int R = -1;
    int count = 0;
    int[] len = new int[init.length];
    for(int i = 0; i < init.length; i++){
        len[i] = (R > i) ? Math.min(len[2 * C - i], R - i) : 1;
        while(i + len[i] < init.length && i - len[i] > -1){
            if(init[len[i] + i] == init[i - len[i]]){
                len[i]++;
            }
            else {
                break;
            }
        }
        if(i + len[i] > R){
            R = i + len[i];
            C = i;
        }
    }
    for (int i : len) {
        count += i / 2;
    }
    return count;
}

public char[] init(String string){
    char[] charArray = string.toCharArray();
    char[] newCharArray = new char[charArray.length * 2 + 1];
    newCharArray[0] = '#';
    for(int i = 1; i < newCharArray.length; i++){
        if(i % 2 == 0){
            newCharArray[i] = '#';
        }
        else{
            newCharArray[i] = charArray[(i - 1) / 2];
        }
    }
    return newCharArray;
}