『LeetCode』解題ノート:005.Longest Palindromic[M]——回文列判断

005.Longest Palindromic [M]

Longest Palindromic M

題

構想

タイトル
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.
構想
使用可能なアルゴリズムはKMPの改良とmanacher(マラ車)アルゴリズムがあり、間違いなくmanacherアルゴリズムは最長子列問題を解決するために専門的に使用され、最も簡便である.このアルゴリズムについて見ることができる:Manacherアルゴリズム

class Solution { 
    public: 
        string longestPalindrome(string s) { 
            //manacher 
            int bound = 0; 
            int id,max_pos=0; 
            int new_len = 2*s.length()+2; 
            vector<int> P(new_len,1); 
            string new_str(new_len-1,'#'); 
            //    ，         ’#’      
            for(int i = 0;i < s.length();i++) 
            { 
                new_str[2*i+1] = s[i]; 
            } 
            new_str = '$'+new_str +='\0'; //     
            //manacher   
            for(int i=1;i < new_len; i++) 
            {
                if(i < bound) 
                { 
                    P[i] = min(bound-i,P[2*id-i]); //      ，     P[id-(i-id)] max_pos-i     
                } 
                 while(new_str[i-P[i]] == new_str[i+P[i]])//               
                    { 
                        P[i]++; 
                    } 
                    //  id bound 
                    if(i+P[i] > bound) 
                    { 
                        bound = i+P[i]; 
                        id = i; 
                    } 

                max_pos = P[i] > P[max_pos]?i:max_pos; 
            } 
            int len = P[max_pos]-1; 
            int start = (max_pos-P[max_pos])/2;
            return s.substr(start,len);
        }
};