PAT (Advanced Level) Practice 1040 Longest Symmetric String (25 分) 凌宸1642
题目描述:
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
.
译:给定一个字符串,您应该输出最长对称子字符串的长度。 例如,给定 Is PAT&TAP symmetric?
,最长的对称子串是 s PAT&TAP s
,因此您必须输出 11
。
Input Specification (输入说明):
Each input file contains one test case which gives a non-empty string of length no more than 1000.
译:每个输入文件包含一个测试用例即给定的一个非空且长度不超过1000的字符串。
output Specification (输出说明):
For each test case, simply print the maximum length in a line.
译:对于每个测试用例,在一行中打印最大的回文串长度。
Sample Input (样例输入):
Is PAT&TAP symmetric?
Sample Output (样例输出):
11
The Idea:
- 经典的、简单的动态规划问题。
The Codes:
#include<bits/stdc++.h>
using namespace std ;
int main(){
string s ;
getline(cin , s) ; // 由于有空格,用 getline 函数比较合适
int len = s.size() , ans = 1 ; // ans 的初始值为 1 是因为最短就是一个字符
bool dp[len][len] ;
memset(dp , 0 , sizeof(dp)) ;
// 边界情况有两种:一种是奇数一种是偶数,奇数的话边界为1个字符 ,偶数的边界为2个字符
for(int i = 0 ; i < len ; i ++) dp[i][i] = true; // 每个字符自身就是回文串
for(int i = 0 ; i < len - 1 ; i ++)
if(s[i] == s[i + 1]){
dp[i][i + 1] = true;
ans = 2 ;
}
for(int l = 3 ; l <= len ; l ++){ // 查找是否有长度为 l 的回文串
for(int i = 0 ; i + l - 1 < len ; i ++){
int j = i + l - 1 ;
if(s[i] == s[j] && dp[i + 1][j - 1]){
dp[i][j] = true ;
ans = l ;
}
}
}
cout << ans << endl ;
return 0 ;
}