https://pintia.cn/problem-sets/994805342720868352/problems/994805446102073344
方法一: 最樸素的做法， 枚舉所有的子串

#include<bits/stdc++.h> using namespace std; int main(void) {string s; getline(cin,s);int ans=0;for(int i=0;i<s.size();i++)//起點{for(int j=1;j<=s.size()-i;j++)//長度{string a=s.substr(i,j);string b=a;reverse(b.begin(),b.end());if(a==b) ans=max(ans,j);}}cout<<ans; }

方法二: 樸素版的優(yōu)化，當(dāng)枚舉的長度已經(jīng)小于我們當(dāng)前保存的答案時，就不用枚舉了。

#include<bits/stdc++.h> using namespace std; int main(void) {string s; getline(cin,s);int ans=0;for(int i=0;i<s.size();i++){for(int j=s.size()-i;j>ans;j--)//從大到小的枚舉長度{string a=s.substr(i,j);string b=a;reverse(b.begin(),b.end());if(a==b) ans=max(ans,j);}}cout<<ans; }

方法三: 雙指針來維護(hù)，時間大幅度的優(yōu)化。

#include<bits/stdc++.h> using namespace std; int main(void) {string s; getline(cin,s);int ans=0;for(int i=0;i<s.size();i++){int l=i-1,r=i+1;//奇數(shù)的情況while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++;//到不相等退出ans=max(ans,r-l+1);//這里多算了2個l=i-1;r=i;//偶數(shù)的情況while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++;ans=max(ans,r-l+1);這里多算了2個}cout<<ans-2; }

總結(jié)

以上是生活随笔為你收集整理的1040 Longest Symmetric String (25 分)【难度: 一般 / 知识点: 最长回文子串】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。