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
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int GetLongestPalindrome(const string& str) {
    string s = "^";
    int ret = 0;
    for (int i=0; i<str.length(); i++) {
        s += '#';
        s += str[i];
    }
    s += "#$";
    int len = s.length();
    int c = 0, r = 0;
    vector<int> vec(len, 0);
    for (int i=1; i<len-1; i++) {
        if (i >= r) {
            vec[i] = 0;
        }
        else {
            int mirror_i = 2*c - i;
            vec[i] = min(vec[mirror_i], r-i);
        }
        while (s[i+vec[i]+1] == s[i-vec[i]-1]) {
            vec[i] += 1;
        }
        if (i+vec[i] > r) {
            c = i;
            r = i+vec[i];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX