求所有以s[i]为中心的奇数回文串

manacher 算法求最长回文子串。时间复杂度O(n)

预处理+运用dp思想。

预处理： 回文串有奇数长度有偶数长度，如果用相同的字符插入每个字符之间及首尾，那么所有的回文串长度都会是奇数。

例如: abcbcba 用|分割得 |a|b|c|b|c|b|a| 以回文串的中心字符作为分割点，左右两个子串的长度是相同的，称他们的长度为回文半径。

dp：

设$dp_i$为以i为中心的回文半径。在可以让我们知道所有以i为中心的奇数长度回文串。这个回文半径不包含中心，也就是说”abcba“，‘c’的回文半径是2。

$d$为遍历到当前回文串最远覆盖的下标，即$d = max(dp_j+j), j \in [0, i-1]$。

设$c$为满足$d = max(dp_j+j), j \in [0, i-1]$的$j$。 在求$dp_i$时，$dp_j,j<i$已经全部求出，对于求$dp_i$：

在$i\le r$时，分两种情况：

1. 当$dp_i \le r$, 这时$dp_i = dp_j$, $j$是$i$关于$m$对称的点。即$dp_i = dp_{i-2m}$
2. 当$dp_i > r$, 对于大于$r$的部分用中心扩散法，所以可以先让$dp_i = r-i$ 由这两种情况可知让$dp_i = min(r-i, dp_{i-2m})$, 然后再做中心扩散法。

在$i>r$时，直接使用中心扩散法。

最后便可求得$dp$数组。以下标$i$为中心的回文串为[i-dp[i]...dp[i]+i], 这个回文串中去除预处理加的分隔符便是原串的回文子串。

// leetcode 5. 最长回文子串
int dp[2005];
string longestPalindrome(string s) {
    string str = "*";
    for (char i:s) {
        str.push_back(i);
        str.push_back('*');
    }
    int n = str.size();
    int d = 0, c = 0;
    for (int i=1; i<n; i++) {
        if (i<=d) dp[i] = min(dp[2*c-i], d-i);
        int l = i-dp[i]-1, r = i+dp[i]+1;
        while (l>=0 && r<n && str[l] == str[r]) {
            l--, r++;
            dp[i]++;
        }
        if (dp[i]+i > d) {
            d = dp[i]+i;
            c = i;
        }
    }
    int mx = *max_element(dp, dp+n);
    for (int i=0; i<n; i++) {
        if (mx == dp[i]) {
            string rt;
            for (int j=i-dp[i]; j<=i+dp[i]; j++) {
                if (str[j] != '*') {
                    rt.push_back(str[j]);
                }
            }
            return rt;
        }
        // cout << i << " " << str[i] << " " << dp[i] << endl;
    }
    return str;
}