LeetCode题解——Longest Palindromic Substring

题目：

给定一个字符串S，返回S中最长的回文子串。S最长为1000，且最长回文子串是唯一。

解法：

①遍历，对于每个字符，计算以它为中心的回文子串长度(长度为奇数)，同时计算以它和右边相邻字符为中心的回文子串长度(长度为偶数)。时间为O(N2)。

②另外，有一个很奇妙的算法，称为Manacher算法，参考 http://www.cnblogs.com/daoluanxiaozi/p/longest-palindromic-substring.html ，时间为O(N)。

代码：

①直接扩展：

 class Solution {

 public:

     string longestPalindrome(string s) {

         int start = , max_len = ;

         for(int i = ; i < s.size(); ++i)

         {

             int left, right, len;

             len = ;    //以当前字符为中心的回文串

             for(left = i - , right = i + ; left >=  && right < s.size() && s[left] == s[right]; --left, ++right)

                 len += ;

             if(len > max_len)

             {

                 start   = left + ;

                 max_len = len;

             }

             len = ;    //以当前字符以及右边相邻字符为中心的回文串

             for(left = i, right = i + ; left >=  && right < s.size() && s[left] == s[right]; --left, ++right)

                 len += ;

             if(len > max_len)

             {

                 start   = left + ;

                 max_len = len;

             }

         }

         return s.substr(start, max_len);

     }

 };

②Manacher算法：

 class Solution {

 public:

     string longestPalindrome(string s) {

         int slen = s.size();

         if(slen ==  || slen == )

             return s;

         const int nslen =  * slen + ;  //每个字符两边填充#，将奇偶长度的回文串统一处理

         string ns(nslen, '#');

         ns[]         = '^';     //开始和结尾添加特殊字符，防止越界

         ns[nslen - ] = '$';

         for(int i = ; i < slen; ++i)

             ns[ * i + ] = s[i];

         int id = , mx = ;  //id为已找到的最右回文串的中心下标，mx为该回文串的最右下标

         int p[nslen];        //p保存以每个字符为中心的回文串的半径，这个半径值就是去掉填充字符之后实际回文串长度

         for(int i = ; i < nslen - ; ++i)

         {

             p[i] = mx > i ? min(mx - i, p[ * id - i]) : ;  //利用已有信息，给当前字符为中心的回文串赋半径初值

             while(ns[i -  - p[i]] == ns[i +  + p[i]])      //向两边扩张

                 ++p[i];

             if(i + p[i] > mx)

             {

                 mx = i + p[i];

                 id = i;

             }

         }

         int mid = , max_len = ;

         for(int i = ; i < nslen - ; ++i)       //找出最长的回文串

             if(p[i] > max_len)

             {

                 mid = i;

                 max_len = p[i];

             }

         return s.substr((mid -  - max_len)/, max_len);   //求出回文串第一个字符的下标，返回回文串

     }

 };

巴特西

LeetCode题解——Longest Palindromic Substring

最新文章

热门文章