AcWing 1524. 最长回文子串

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1524. 最长回文子串原题链接简单

作者：

leo123456 , 2020-08-30 15:43:57 , 所有人可见 , 阅读 3355

20

8

//双指针，往两边走，子串分奇偶
#include<iostream>
#include<cstring>

using namespace std;

int main()
{
    string str;
    getline(cin,str);

    int res=0;
    for(int i=0;i<str.size();i++)
    {
        int l=i-1,r=i+1;
        while(l>=0&&r<str.size()&&str[l]==str[r]) l--,r++;
        res=max(res,r-l-1);

        l=i,r=i+1;
        while(l>=0&&r<str.size()&&str[l]==str[r]) l--,r++;
        res=max(res,r-l-1);
    }
    cout<<res<<endl;

    return 0;
}

8 评论

坚持可贵 2023-10-06 20:15

这时间复杂度怎么看

盛-_-夏 2022-04-20 19:59

tql

Mr.lonely_6 2022-01-22 12:23

#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N = 1010;
int dp[N][N];
string s;
int main() {
getline(cin, s);
int n = s.length();
int maxLen = 1;
for(int i = 0; i < n;i) dp[i][i] = 1; // 单个字符也是回文串
for(int L = 2; L <= n; L) { // 遍历长度
for(int i = 0 ;i < n;i++) { // 遍历起点
int j = i + L - 1; // 终点
if(j >= n) break;
if(s[i] != s[j]) dp[i][j] = dp[i+1][j-1];
else if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
maxLen = max(maxLen, dp[i][j]);
}
}
cout <<maxLen << endl;
return 0;
}
大佬，为什么我这个代码不行