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<iostream>
#include<algorithm>
using namespace std;
string preProcess(const string &s){
    int n = s.size();
    if (n == 0) return "^$";
    
    string T = "^";
    for (int i = 0; i < n; i++){
        T += '#';
        T += s[i];
    }
    T += "#$";
    return T;
}
int longestPalindrome(const string &s){
    string T = preProcess(s);
    int n = T.size();
    int *P = new int[n];
    int C = 0, R = 0;
    
    for (int i = 1; i < n - 1; i++){
        int i_mirror = 2 * C - i;
        P[i] = (R>i) ? min(R - i, P[i_mirror]) : 0;
        while (T[i - 1 - P[i]] == T[i + 1 + P[i]])
            P[i]++;
        if (i + P[i] > R){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX