PAT (Advanced Level) Practice 1040 Longest Symmetric String (25 分) 凌宸1642

本文主要是介绍PAT (Advanced Level) Practice 1040 Longest Symmetric String (25 分) 凌宸1642，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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 ;
}

这篇关于PAT (Advanced Level) Practice 1040 Longest Symmetric String (25 分) 凌宸1642的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！