最长回文子串问题（四种方法）

// 判断给定字符串是否是回文串
bool IsPalindromicString(char *s) {
    int n = strlen(s);
    int left = 0;
    int right = n - 1;

    while (left < right) {
        if (s[left] == s[right]) {
            left++;
            right--;
        } else {
            return false;
        }
    }
    return true;
}

// 辅助函数：从长度为 n 的字符串 s 的给定位置左右扩展寻找回文串。
// 输入的 left 和 right 是扩展的左右起始位置。
// 返回扩展经过的字符数 k .
int ExpandPalindrome(char *s, int n, int left, int right) {
    int k = 0;
    while (left >= 0 && right < n) {
        if (s[left] == s[right]) {
            left--;
            right++;
            k++;
        } else {
            break;
        }
    }
    return k;
}

// 返回给定字符串 s 的最长回文子串的长度
int LongestPalindromicSubstring(char *s) {
    int n = strlen(s);

    if (n <= 0) return 0;

    // 记录最大回文子串的长度
    // 一旦 s 非空，必然最大回文子串长度至少为 1
    int max_length = 1;

    for (int i = 0; i < n; i++) {
        // 考察回文串长度是奇数的情况
        int k1 = ExpandPalindrome(s, n, i - 1, i + 1);
        // 考察回文串长度是偶数的情况
        int k2 = ExpandPalindrome(s, n, i, i + 1);

        // 计算两个情况下的长度
        int length1 = k1 * 2 + 1;
        int length2 = k2 * 2;

        // 更新最大值
        if (length1 > max_length) max_length = length1;
        if (length2 > max_length) max_length = length2;
    }

    return max_length;
}

// 返回给定字符串 s 的最长回文子串的长度
int LongestPalindromicSubstring(char *s) {
    int n = strlen(s);

    if (n <= 0) return 0;

    // dp[j] 表示以位置 j 结尾的最长回文子串的起始位置
    // 其长度就是 j - dp[j] + 1
    int dp[n];
    dp[0] = 0;

    // 记录最大回文子串的长度
    // 0 - 0 + 1
    int max_length = 1;

    for (int j = 1; j < n; j++) {
        if (dp[j - 1] > 0 && s[j] == s[dp[j - 1] - 1]) {
            // 当前位置的字符和上一次回文串的左邻字符相同
            // 回文串得到扩展
            dp[j] = dp[j - 1] - 1;
        } else {
            // 从左向右找
            int left = dp[j - 1];
            int right = j;
            int start = left;  // 最近一次的回文查找起始位置

            while (left < right) {
                if (s[left] != s[right]) {
                    // 遭遇失配字符，重置 right
                    right = j;
                    start = left + 1;
                } else {
                    // 否则，两边继续收拢
                    right--;
                }
                left++;
            }

            dp[j] = start;
        }

        // 更新最大值
        int length = j - dp[j] + 1;
        if (length > max_length) max_length = length;
    }

    return max_length;
}

// 返回给定字符串 s 的最长回文子串的长度
int LongestPalindromicSubstring(char *s) {
    int n = strlen(s);

    if (n <= 0) return 0;

    // dp[i][j] 表示 s[i..j] 是否回文，j >= i
    bool dp[n][n];

    // 初始化
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) dp[i][j] = false;

    // 易知，单个字符 s[i..i] 构成回文
    for (int i = 0; i < n; i++) dp[i][i] = true;

    // 记录最大回文子串的长度，至少为 1
    int max_length = 1;

    // 考虑递推
    // 主要的递推关系是 dp[i][j] = dp[i+1][j-1]
    // 所以倒序遍历 i ，才可以形成递推
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j]) {
                if (j - 1 >= i + 1) {  // 子串 s[i+1..j-1] 有效性
                    if (dp[i + 1][j - 1]) dp[i][j] = true;
                } else {
                    // 此时 j < i + 2 即 j <= i+1
                    // 再之 s[i] == s[j]，必回文
                    dp[i][j] = true;
                }
            }

            if (dp[i][j]) {
                // 更新最大长度
                int length = j - i + 1;
                if (length > max_length) max_length = length;
            }
        }
    }
    return max_length;
}

// 预处理过程，n 是原字符串 s 的长度
// 预期结果 s1 的长度是 2n + 1
// 例如 "aba" => "|a|b|a|"
void ManacherPreprocess(char *s, int n, char *s1) {
    int i = 0;
    int j = 0;
    while (i < n) {
        s1[j++] = '|';
        s1[j++] = s[i++];
    }
    // 末尾补 '|'
    s1[j++] = '|';
}

#define min(x, y) (x) < (y) ? (x) : (y)

// Manacher 算法主过程
// 输入长度为奇数的已预处理过的字符串 s 和其长度 n
// 返回最长回文串的半径
int Manacher(char *s, int n) {
    // 最长回文串半径的数组
    int p[n];
    // 显然 第一位的半径是 0
    p[0] = 0;
    // 追踪数组 p 的最大值
    int max_p = 0;

    // 维护向右延伸最远的回文串的信息
    // 其最右的位置 r
    int r = 0;
    // 其中心位置 c
    int c = 0;

    // 求解数组 p
    for (int i = 1; i < n; i++) {
        // 找出 i 为中心的回文串半径 p[i]
        if (i < r) {
            // 目标回文串的中心在 r 左边时
            // 最大化吸收已有信息

            // j 是 i 关于 c 对称的位置
            int j = c - (i - c);

            // p[i] 至少为下面二者最小值
            p[i] = min(p[j], r - i);
        } else {
            // 否则，初始化 p[i]
            p[i] = 0;
        }

        // 左右进行扩展，探测剩余长度
        int left = i - p[i] - 1;
        int right = i + p[i] + 1;

        while (s[left] == s[right] && left >= 0 && right < n) {
            left--;
            right++;
            p[i]++;
        }
        // 真实的 right
        // 因上面的循环跳出后的 right 可能稍大
        right = i + p[i];

        // 维护 c 和 r
        if (right > r) {
            r = right;
            c = i;
        }

        // 维护最大值
        if (max_p < p[i]) max_p = p[i];
    }
    return max_p;
}

// 返回给定字符串 s 的最长回文子串的长度
int LongestPalindromicSubstring(char *s) {
    int n = strlen(s);
    if (n <= 0) return 0;

    // 预处理
    int n1 = 2 * n + 1;
    char s1[n1];
    ManacherPreprocess(s, n, s1);

    // s1 的回文半径 就是 s 的回文长度
    return Manacher(s1, n1);
}

function Manacher
    for i < n  // 外层循环
        if i < r
            p[i] = min(p[j], r - r)
        else
            p[i] = 0

        left = i - p[i] - 1
        right = i + p[i] + 1

        while (s[left] == s[right])  // 内层循环
            left--
            right++
            p[i]++

        if right > r
            r = right