$”

    算法的核心思想就是，可以看到中间“abacaba”是最长回文，当我们已经算到了 “c” 的位置，知道p[9] = 5（如果我没算错的话- -），那当我们算 “p” 这个位置的时候，发现“p”位置的下标减去 “c” 的下标，大于“c”位置（center）的值，也就是在以“c”为中心的最长回文串的外边，那么我们肯定是不知道什么对“p”位置的值有贡献的东西，只能用第一种方法，中心扩充，来计算这个位置的值。

    但是！如果我们要算 “c” 后边的 “b” 的值的时候，我们知道了这个 “b” 是处在 “c” 的回文子串之中的，所以如果它的下标是 i，那么它对应过去的下标 mirror_i 位置上一定也是b，这时候需要判断对应位置上的回文值，因为对应位置一定已经计算过了，所以通过镜像过去位置上的回文值计算当前位置的回文值，能够避免掉很多运算！

    如果对应位置的回文长度不如 “c” 的回文长度长，那么当前位置的一定也就是那么长，因为是镜像的！下图就是实例：

    但是如果镜像位置上的回文长度超出了 “c” 辐射的范围，那么当前位置上的就是至少能够达到碰到 “c” 辐射范围的边缘。如下图所示。

    总结来说，就是在从左往右遍历整个字符串的过程中，通过已有信息，跳过不必要的判断，共有三种情况：

    1、要计算的位置在已知最大的回文串覆盖范围外 —— 只能通过中心扩展一点一点算，没有跳过计算；

    2、要计算的位置在已知最大回文串覆盖范围内，且镜像位置上的回文串被最大回文串包含 —— 不需要计算，直接 p[i] = p[mirror_i] 即可，跳过这个位置所有计算；

    3、要计算的位置在已知最大回文串覆盖范围内，但镜像位置上的回文串没有完全被最大回文串包含 —— 可以从最大回文串的边缘开始中心扩充，能跳过一部分计算。

    看懂了算法思想，代码就比较简单了：

// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s)
{
    int n = s.length();
    if (n == 0) return "^$";
    string ret = "^";
    for (int i = 0; i < n; i++)
        ret += "#" + s.substr(i, 1);
    ret += "#$";
    return ret;
}
 
string longestPalindrome(string s)
{
    string T = preProcess(s);
    int n = T.length();
    int *P = new int[n];
    int C = 0, R = 0;                 // center, right
    for (int i = 1; i < n-1; i++)
    {
        int i_mirror = 2 * C - i;     // equals to i' = C - (i-C)
        P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
        // Attempt to expand palindrome centered at i
        while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
            P[i]++;
        // If palindrome centered at i expand past R, adjust center based on expanded palindrome.
        if (i + P[i] > R)
        {
            C = i;
            R = i + P[i];
        }
    }
    // Find the maximum element in P.
    int maxLen = 0;
    int centerIndex = 0;
    for (int i = 1; i < n-1; i++)
    {
        if (P[i] > maxLen)
        {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    delete[] P;
    return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
}

     由于这个算法其实最关心的就是 right 边界，每次就是移动 R， 算法可以保证 finish in 2 * n steps（具体为什么是2*n还没有很明白），所以是 O(N) 的时间富足度。

方法四：后缀树（Suffix Trees）

    并没有看