PAT (Advanced Level) Practice 1040 Longest Symmetric String (25分)
PAT (Advanced Level) Practice 1040 Longest Symmetric String (25分)
1040 Longest Symmetric String (25分)
Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.
Input Specification:
Each input file contains one test case which gives a non-empty string of length no more than 1000.
Output Specification:
For each test case, simply print the maximum length in a line.
Sample Input:
Is PAT&TAP symmetric?Sample Output:
11题意：给定一个字符串，在它的子串（可能是它自己）中找一个最大长度的回文串，输出其长度即可
分析：回文串长度有奇数和偶数两种情况，所以总共要考虑三种情况（为什么见下面分析）
奇数的时候应该这样讨论：遍历一遍字符串，扫描到当前字符，以当前字符为中心左扩大和右扩大如果相等，以该处为中心的最大字符串长度+2,(初始长度为1，因为本身就是个回文串)，每次每一个位置字符处理完都有一个该点最大字符串长度，记为max1
偶数的时候应该这样讨论：
1.扫描到当前字符，若当前字符和后一个字符相同，以当前字符和后一个字符为中心为中心左扩大和右扩大如果相等，以该处为中心的最大字符串长度+2(初始长度为2，因为当前字符和后一个字符相同)，每次每一个位置字符处理完都有一个该点最大字符串长度，记为max2
2.扫描到当前字符，若当前字符和前一个字符相同，以当前字符和前一个字符为中心为中心左扩大和右扩大如果相等，以该处为中心的最大字符串长度+2(初始长度为2，因为当前字符和前一个字符相同)，每次每一个位置字符处理完都有一个该点最大字符串长度，记为max3
取ans=max(ans,max1,max2,max3)即可~
#include<bits/stdc++.h>
#define ll long long
#define rg register long long
using namespace std;
string s;
ll maxx=1;
int main()
{
getline(cin,s);
for(rg i=0;s[i];i++)
{
//cout<<s[i]<<endl;
ll x=i-1,y=i+1,max1=1,max2=0,max3=0;
while(x>=0&&y<s.size()&&s[x]==s[y])
{
//cout<<s[x]<<" "<<s[y]<<endl;
x--,y++;
max1+=2;
}
if(i-1>=0&&s[i-1]==s[i])
{
max2=2;
ll x1=i-2,y1=i+1;
while(x1>=0&&y1<s.size()&&s[x1]==s[y1])
{
x1--,y1++;
max2+=2;
}
}
if(i+1<s.size()&&s[i+1]==s[i])
{
max3=2;
ll x1=i-1,y1=i+2;
while(x1>=0&&y1<s.size()&&s[x1]==s[y1])
{
x1--,y1++;
max3+=2;
}
}
maxx=max(maxx,max(max1,max(max2,max3)));
}
cout<<maxx<<endl;
while(1)getchar();
return 0;
}腾讯云开发者
