当前位置: 代码迷 >> 综合 >> pta--1040 Longest Symmetric String(25 分)(最长回文串问题)
  详细解决方案

pta--1040 Longest Symmetric String(25 分)(最长回文串问题)

热度:51   发布时间:2023-12-26 10:09:23.0

题目:https://pintia.cn/problem-sets/994805342720868352/problems/994805446102073344

【分析】

题意:求最长对称(回文)串的长度

思路:枚举回文串的中间位置i,然后不断的往外扩展,直到有字符不同。

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;getline(cin,s);int len=s.length();int maxl=0;int x=0,y=0;for(int i=0;i<len;i++){for(int j=0;i-j>=0&&i+j<len;j++){if(s[i-j]!=s[i+j])break;if(j*2+1>maxl){maxl=2*j+1;//	x=i-j;y=i+j;}	}for(int j=0;i-j>=0&&i+j+1<len;j++){if(s[i-j]!=s[i+j+1])break;if(j*2+2>maxl){maxl=j*2+2;//x=i-j;y=i+j+1;}}}
//	cout<<x<<","<<y<<endl;cout<<maxl<<endl;
}

 

  相关解决方案