manacher算法

解决的问题

字符串的最长回文字串的问题（必须是连续的串）
获得长度为奇数和偶数的字符串
奇数的话直接取每个字符向两边找扩展即可
针对偶数可以在每两个字符之间加入一个虚拟的字符，向左右两边扩展得到偶数长度的回文字符串
将处理得到的字符串的长度直接/2就可以得到实际的回文串的长度
虚拟的字符可以是任意字符，即使是原串之中出现过的字符也可以
时间复杂度是O(N^2)
Manacher
时间复杂度是O(N)
概念
- 回文直径和半径
- 回文直径7半径4
- 生成一个回文半径数组
- 之前扩展的所有位置中所到达过的回文最右边界，初始值是-1
- 取得最远边界的时候的中心点的位置，与上一条同时更新

方法：

假如此时index没在最右回文右边界之内，直接向两边暴力计算即可

假如在最右边界之内：

中心点一定在index的左侧
C是此时的最右回文串的中心位置，L是左边界，R是右边界
i’是i关于C的对称点，根据i’的回文状况分类：
- 假如i’的回文在L和R范围内（用回文半径数组得到）
  - i位置和i’位置的回文半径相同
- 假如i’的区域有一部分已经到L和R的外侧了
  - 此时i的答案是i到R的长度
- 假如i’的左边界正好在L上
  - 首先i’自身的回文半径一定是回文，从R外的第一个字符开始继续验证即可

manacher代码

public static int manacher(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    // "12132" -> "#1#2#1#3#2#"
    char[] str = manacherString(s);
    // 回文半径的大小
    int[] pArr = new int[str.length];
    int C = -1;
    // 讲述中：R代表最右的扩成功的位置
    // coding：最右的扩成功位置的，再下一个位置
    int R = -1;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < str.length; i++) { // 0 1 2
        // R第一个违规的位置，i>= R
        // i位置扩出来的答案，i位置扩的区域，至少是多大。
        pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
        while (i + pArr[i] < str.length && i - pArr[i] > -1) {
            if (str[i + pArr[i]] == str[i - pArr[i]])
                pArr[i]++;
            else {
                break;
            }
        }
        if (i + pArr[i] > R) {
            R = i + pArr[i];
            C = i;
        }
        max = Math.max(max, pArr[i]);
    }
    return max - 1;
}

public static char[] manacherString(String str) {
    char[] charArr = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for (int i = 0; i != res.length; i++) {
        res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    }
    return res;
}

// for test
public static int right(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    char[] str = manacherString(s);
    int max = 0;
    for (int i = 0; i < str.length; i++) {
        int L = i - 1;
        int R = i + 1;
        while (L >= 0 && R < str.length && str[L] == str[R]) {
            L--;
            R++;
        }
        max = Math.max(max, R - L - 1);
    }
    return max / 2;
}

解决的问题

获得长度为奇数和偶数的字符串

Manacher

manacher代码