回文子串

O(n)
 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         string s2 = "";
 7         for (int i = 0; i < s.size(); ++i)
 8             s2 = s2 + "#" + s[i];
 9         s2 += "#";
10         int* r = new int[s2.size() + 2];
11         memset(r, 0, s2.size() + 2);
12         int maxPosition = 0, position = 0;
13         int lp = 0, lr = 0;
14         for (int i = 1; i < s2.size(); ++i) {
15             if (i < maxPosition) {
16                 r[i] = maxPosition - i;
17                 if (r[i] > r[2 * position - i])
18                     r[i] = r[2 * position - i];
19             }
20             else
21                 r[i] = 1;
22             while ((i - r[i] > -1 && i + r[i] < 2 * s.size() + 1) && s2[i - r[i]] == s2[i + r[i]]) r[i]++;
23             if (r[i] + i > maxPosition) {
24                 maxPosition = r[i] + i;
25                 position = i;
26             }
27             if (r[i] > lr) {
28                 lr = r[i];
29                 lp = i;
30             }
31         }
32         string result = "";
33         for (int i = lp - lr + 1; i < lp + lr; ++i) {
34             if (s2[i] != '#')
35                 result += s2[i];
36         }
37         return result;
38     }
39 };