leetcode 5. 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.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
求最长回文子串并输出
直接马拉车算法就ok了，时间复杂度是O(n)
代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        string t = "*";
        int n = 2 * s.size() + 1;
        for (int i = 0; i < s.size(); ++i) {
            t += '#';
            t += s[i];
        }
        vector<int> p (n);
        t += '#';
        int id, mx = 0, ans = 0, ok;
        for (int i = 1; i <= n; ++i) {
            if (mx > i) 
                p[i] = min(p[2 * id - i], mx - i);
            else 
                p[i] = 1;
            while (t[i + p[i]] == t[i - p[i]]) ++p[i];
            if (p[i] + i > mx) {
                mx = p[i] + i;
                id = i;
            }
            if (p[i] > ans) {
                ans = p[i];
                ok = id;
            }
        }
        string v = "";
        --ans;
        //cout << ans << " " << ok <<endl;
        for (int i = ok - ans; i <= ok + ans; ++i) {
            if (t[i] != '#' && t[i] != '*') v += t[i];
        }
        return v;
    }
};