本題我采用從不同中心不斷擴展的方法去進行求解，程式代碼如下，在寫程式的時候我遇到的一個坑是，由于string的length()函式回傳值并非int型數值，因此一開始直接使用min()函式會報錯，經過強制型別轉換后便可以不報錯，時間復雜度為O(n)馬拉車演算法留作以后再進行學習～～～～～
#include <iostream> #include <cstdio> #include <string> #include <algorithm> using namespace std; string longestPalindrome(string s); int main() { string s; cin>>s; cout<<longestPalindrome(s); return 0; } string longestPalindrome(string s) { if(s.length()==0) return ""; int max_length = 0; int ex = 0; int position = 0; bool flag = false; for(int i = 0;i<s.length();++i) { int expand = 0; while(expand<= min(i, (int)(s.size()-1-i))) { if(s[i+expand]==s[i-expand]) { if(expand*2+1>max_length) { max_length = expand*2+1; ex = expand; position = i; expand++; } else expand++; } else break; } } string ans = s.substr(position-ex,max_length); for(int i = 1;i<s.length();++i) { int expand = 1; while(expand<= min(i, (int)(s.size()-i))) { if(s[i+expand-1]==s[i-expand]) { if(expand*2>max_length) { max_length = expand*2; if(!flag) flag = true; ex = expand; position = i; expand++; } else expand++; } else break; } } if (flag) { ans = s.substr(position-ex,max_length); } return ans; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40805.html
標籤：C++
下一篇：Z 字形變換