马拉车算法

思路

• 使用马拉车（Manacher）算法

Code

class Solution {
public:
    int d[2002] = { 0 };
    string longestPalindrome(string s) {

        string s2 = "$#";
        int n = s.length();
        s2.reserve(n * 2 + 2);

        for (int i = 0; i < n; ++i)
        {
            s2 += s[i];
            s2 += '#';
        }
        int N = s2.length()-1;
        d[1] = 1;
        int M = 0;
        int P = 0;
        for (int i = 2, l=0, r = 1; i <= N; ++i)
        {
            if (i <= r) d[i] = min(d[r - i + l], r - i + 1);
            while (s2[i - d[i]] == s2[i + d[i]])d[i]++;
            if (i + d[i] - 1 > r) l = i - d[i] + 1, r = i + d[i] - 1;

            if (M < d[i])
            {
                M = d[i];
                P = i;
            }
        }
         int L = (P-1) / 2 ;
         return s.substr(L-(d[P]-1)/2, d[P]-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34