马拉车(Manacher)算法

解决的问题

马拉车算法主要是为了解决求一个字符串的最长回文串，当然求解这个问题的算法很多，比如穷举法（轮询所有子串得出最长的是回文串子串），但是时间复杂度太高（复杂度为O(n^3)）。马拉车算法可以有效的降低时间复杂度（复杂度为O(n)）。

原理与实现

原理

利用已知的对称信息和回文串的对称性得出其他位置的对称信息，并且不用考虑字符串长度是奇数还是偶数的，因为首先我们对字符串进行处理：在字符串的首尾和字符间加上"#"，如"nbbn"改变后为"#n#b#b#n#"，再在首位加上"&"，所以最终经过处理的字符串为"&#n#b#b#n#"。另外我们还需要辅助一个和处理后长度一致的int数组，该数组用来存字符串对应位置的最长回文长度加上本身（就是最长回文数+1），如下：

如字符串第二个b两边对称的长度为1，所以它对应的int数组内的值为2。有了这个表格，我们就知道，只要求出字符串对应位置上int数组的值，那么回文串自然就出来了，那int[]数组怎么求出来呢？也就是怎么利用已知的对称信息和回文串的对称性得出其他位置的对称信息呢？首先假设最长回文所在位置为id，到最长回文长度的位置为idMax,如果我们要求i位置上的最长回文长度（也就是int[i]的值），可以根据int[j]的值，前提条件是(0<=j<i,所以int[j]是已知的)，那么是什么原理呢？分为两种情况：

i <= idMax，通过id的位置找到和i位置对称的j点

如过int[j] < idMax - i，那么int[i]就等于int[j]。

如果int[j] >= idMax - i，那么int[i]的值大于或者等于int[j]。然后再在这个位置继续向左右延伸判断是否还有回文长度。

i > idMax时，所以中心点为i的回文还没有匹配，只有通过循环去匹配了。

实现

这里就直接用Java代码实现了，每一次算出当前位置的回文长度后，要更新相关信息：

public static String longestPalindrome(String s) {
    if (s.length() <= 1){
        return s;    
    } 
    StringBuilder stringBuilder = new StringBuilder("$");
    for (char c : s.toCharArray()) {
        stringBuilder.append("#");
        stringBuilder.append(c);
    }
    stringBuilder.append("#");
    String str = stringBuilder.toString();

    int id = 0;
    int idMax = 0;
    int index = 0;
    int maxLength = 0;

    int p[] = new int[str.length()];

    for (int curr = 1; curr < str.length(); curr++) {
        int j = 2 * id - curr;

        // p[curr] = idMax > curr ? Math.min(p[symmetryId], idMax - curr) : 1;
        // 更容易理解的写法
        if (idMax > curr) {
            if (p[j] < idMax - curr)
                p[curr] = p[j];
            else
                p[curr] = idMax - curr;
        } else {
            p[curr] = 1;
        }

        while (curr + p[curr] < str.length() && str.charAt(curr + p[curr]) == str.charAt(curr - p[curr])) {
            p[curr]++;
        }

        if (curr + p[curr] > idMax) {
            id = curr;
            idMax = curr + p[curr];
        }

        if (p[curr] > maxLength) {
            maxLength = p[curr];
            index = curr;
        }
    }
    return s.substring((index - maxLength) / 2, (index + maxLength) / 2 - 1);
}