LintCode-最長回文子列

最長1000の長さを仮定する文字列を与え、その最長回文サブ列を求め、条件を満たす最長回文列が1つしかないと仮定することができます.
実際の面接でこの問題に遭遇したことがありますか? 
Yes
サンプル
文字列"abcdzdcab"が与えられ、その最長回文サブ列は"cdzdc"である.
に挑戦
O(n 2)時間の複雑さのアルゴリズムは受け入れられ、O(n)のアルゴリズムを使うことができれば自然にもっといいです.
タブ
Expand  
関連テーマ
Expand 
解析:遍manacherアルゴリズムを書いてみました.ここでp[i]はiを中心とし、iを含む半径を表す
コード:

class Solution {
public:
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    string longestPalindrome(string& s) {
        // Write your code 
        string news = "$#";
        for(int i=0;i<s.length();i++)
		{
            news+=s[i];
			news+="#";
		}
        vector<int> p(news.length(),0);
        int mx = 0;
        int id = 0;
        int retid = 0;
        int maxp = 0;
        for(int i=0;i<news.length();i++)
        {
            if(mx>i)
            {
                p[i] = min(mx-i,p[2*id-i]);
            }
            else
                p[i] = 1;
            while(i-p[i]>=0&&news[i+p[i]]==news[i-p[i]])
                p[i]++;
            if(i+p[i]>mx)
            {
                mx = i+p[i];
                id = i;
            }
            if(p[i]>maxp)
            {
                maxp = p[i];
                retid = i;
            }
        }
        string ret = "";
        for(int i=retid-p[retid]+1;i<=retid+p[retid]-1;i++)
            if(news[i]!='#')
                ret+=news[i];
        return ret;
    }
};