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, and there exists one unique longest palindromic substring.
ここでは、効率の高い2つの方法を示します.
方法1:動的計画法O(n 2)

class Solution {
public:
    string longestPalindrome(string s) {
        int maxbeg=0,maxlen=0;
        if(s.size()==0||s.size()==1)
            return s;
        bool flag[1000][1000]={false};
        for(int i=0;i<1000;i++)
            flag[i][i]=true;
        for(int i=0;i<s.size()-1;i++){
            if(s[i]==s[i+1]){
                flag[i][i+1]=flag;
                maxbeg=i;
                maxlen=2;
            }
        }
            
        for(int len=3;len<=s.size();len++){
            for(int i=0;i+len-1<s.size();i++){
                int beg=i,end=i+len-1;
                if(s[beg]==s[end]&&flag[beg+1][end-1]){
                    flag[beg][end]=true;
                    maxbeg=beg;
                    maxlen=len;
                }
            }
        }
        return s.substr(maxbeg,maxlen);
    }
};

方法2:ManacherアルゴリズムO(n)は,回文の対称性を利用して回文列の半径を解くことを核心思想とする.原列を改造することを実現する

class Solution {
public:
    string longestPalindrome(string s) {
        string str;
        str+='$';
        for(int i=0;i<s.size();i++)
            str=str+'#'+s[i];
        str+='#';
        
        int mid=0,mx=0,maxi=1;
        int p[str.size()];
        for(int i=1;i<str.size();i++){
            if(mx>=i)
                p[i]=min(p[2*mid-i],mx-i+1);
            else
                p[i]=1;
            
            int beg=i-p[i],end=i+p[i];
            while(str[beg]==str[end]){
                p[i]++;
                beg--;
                end++;
            }
            
            if(p[i]+i-1>mx){
                mx=p[i]+i-1;
                mid=i;
            }
            
            maxi=p[i]>p[maxi]?i:maxi;
        }
        
        return s.substr((maxi-p[maxi]+1)/2,p[maxi]-1);
    }
};

Manacherアルゴリズムの具体的な説明は以下を参照してください.http://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html