利用中心擴展法求最長回文子串算法復雜度為O（）

待改進：Manacher方法，Manacher 法將所有的字符串全部變成奇數個字符。

思想：回文子串一定是個中心對稱的圖形，有的對稱中心是一個字母比如abcba，有的是對稱中心是兩個字母比如abba。所以需要分開進行（程序中會有體現）。利用回文子串的這一特點我們可以假設回文子串的每一個子串都是對稱中心，然后看看對稱中心的左右是否是一樣的，如果是一樣的證明該段字符串是回文只需要求這段長度，標記開始的位置然后表示出這一段字符即可。

class Solution { public:string longestPalindrome(string s) {int len=s.size();if(len==1)return s;//只有一個字母的情況int start=0;//記錄回文子串開始的位置int end=0;int mlen=0;//記錄回文子串的長度for(int i=0;i<len;i++){int len1=findhw(s,i,i);//對稱中心為一個字母int len2=findhw(s,i,i+1);//對稱中心為兩個字母mlen=max(max(len1,len2),mlen);if(mlen>end-start+1){start=i-(mlen-1)/2;end=i+mlen/2;}}return s.substr(start,mlen);}private:int findhw(string s,int left,int right){int l=left;int r=right;while(l>=0&&r<s.length()&& s[l]==s[r]){l--;r++;}//從第一個假對稱中心向后找，直到找到真的為止return r-l-1;} };

參考資源：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-c-by-gpe3dbjds1/

總結

以上是生活随笔為你收集整理的求最长回文子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。