【暴力枚舉】

求最長回文串最容易的方法就是暴力枚舉，求出字符串的每一個子串，然后判斷是不是回文，找到最長的那個回文串

求每一個子串的時間復雜度為 O(N^2)，判斷一個子串是不是回文時間復雜度為 O(N)，總的時間復雜度為 O(N^3)

string str; void longestPalindrome(){int len=str.size();//字符串長度int maxlen=1;//最長回文串長度int start=0;//最長回文串起始地址for(int i=0;i<len;i++){//起始地址for(int j=i+1;j<len;j++){//結束地址//判斷是不是回文int temp1=i,temp2=j;while(temp1<temp2 && str.at(temp1)==str.at(temp2)){temp1++;temp2--;}if(temp1>=temp2&&j-i+1>maxlen){start=i;//更新回文串起始地址maxlen=j-i+1;//更新回文串長度}}}str=str.substr(start, maxlen); } int main(){cin>>str;longestPalindrome();cout<<str<<endl;;return 0; }

【中心擴展法】

中心擴展就是將給定的字符串的每一個字母當做中心，然后向兩邊擴展，這樣來尋找最長的回文串。其需要考慮兩種情況：長度為奇數的回文串、長度為偶數的回文串。

時間復雜度為 O(N^2)

string str; void longestPalindrome(){int len=str.size();//字符串長度int maxlen=1;//最長回文串長度int start=0;//最長回文串起始位置//長度為奇數的回文串for(int i=0;i<len;i++){//枚舉中心位置int left=i-1,right=i+1;//以i為中心向左右兩邊擴展while(left>=0 && right<len && str.at(left)==str.at(right)){if(right-left+1>maxlen){start=left;//更新回文串起始位置maxlen=right-left+1;//更新回文串長度}left--;right++;}}//長度為偶數的回文串for(int i=0;i<len;i++){//枚舉中心位置int left=i,right=i+1;//以i為中心向左右兩邊擴展while(left>=0 && right<len && str.at(left)==str.at(right)){if(right-left+1>maxlen){start=left;//更新回文串起始位置maxlen=right-left+1;//更新回文串長度}left--;right++;}}str=str.substr(start, maxlen); } int main(){cin>>str;longestPalindrome();cout <<str<<endl;return 0; }

【動態規劃】

設?dp[j][i] 表示從?j 到?i 的子串是否是回文串，則：

當 dp[j][i]=true 時，表示從 j 到 i 的子串為回文子串，且子串起點位置為 j，長度為 i - j + 1

時間復雜度為：O(N ^ 2)

string str; bool dp[N][N]; void longestPalindrome(){memset(dp,false,sizeof(dp));int len=str.size();//字符串長度int start=0;//最長回文子串起點int maxlen=1;//最長回文子串長度for(int i=0;i<len;i++){//字符串終點for(int j=0;j<=i;j++){//字符串起點if(i-j<2)dp[j][i]=(str[i]==str[j]);elsedp[j][i]=(str[i]==str[j] && dp[j+1][i-1]);if(dp[j][i] && maxlen<i-j+1){start=j;//更新回文串起點maxlen=i-j+1;//更新回文串長度}}}str=str.substr(start, maxlen); }int main(){cin>>str;longestPalindrome();cout<<str<<endl;return 0; }

【Manacher 算法】

時間復雜度：O(N)

算法詳解：點擊這里

?

總結

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

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