Day 51, #5, Longest Palindromic Substring(*) ATTENTION NEEDED

Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
 -------------------------------------------
Solution#1 O(n^2),
there are (2n - 1) centers for all possible palindromes

class Solution {
public:
    void pal (string s, int &left, int &right, int &maxLeft,int &maxRight) {
        while (left >= 0 && right < s.length()) {
            if (s[left] == s[right]) {
                left--;
                right++;
            }else {
                break;
            }
        }
        if (maxRight - maxLeft < right - left - 2) {
                maxLeft = left + 1;
                maxRight = right - 1;
        }
    }

    string longestPalindrome(string s) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (s.length() == 1) return s;
        int maxLeft = 0;
        int maxRight = 0;
        int center = 1;
        int max = 0;
        for (;center < s.length(); center++) {
            int left = center - 1;
            int right = center;
            pal(s,left,right,maxLeft,maxRight); // even
            left = center - 1;;
            right = center + 1;
            pal(s,left,right,maxLeft,maxRight); // odd
        }
        return s.substr(maxLeft,maxRight - maxLeft + 1);
    }
};

Solution#2 O(n) 
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
Jun-27-2015
Manacher's algorithm

class Solution {
public:
    string processString(string s) {
        if (s.length() == 0) return s;
        string rt = "";
        for (int i = 0; i < s.length(); i++) {
            rt = rt + "#" + s[i];
        }
        rt += '#';
        return rt;
    }

    string longestPalindrome(string s) {
        string t = processString(s);
        vector<int> p(t.length(),0);
        int center = 1, rightExpand = 1;
        
        for (int i = 1; i < t.length(); i++) {
            int i_mirror = center - (i - center); 
            if (rightExpand > i) {
                p[i] = min(rightExpand - i,p[i_mirror]);
            }
            
            while (i + 1 + p[i] > 0 && i + 1 + p[i] < t.length() && t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
                cout << p[i] << endl;
                p[i]++;
            }
            
            if (i + p[i] > rightExpand) {
                rightExpand = i + p[i];
                center = i;
            }
        }
        
        int longest = 0;
        int index = 0;
        for (int i = 0; i < p.size(); i++) {
            if (longest < p[i]) {
                index = i;
                longest = p[i];
            }
        }
        return s.substr((index - longest) / 2, longest);
    }
};