(PAT 1040) Longest Symmetric String (DP-最长回文子串)

悠悠 2022-03-19 10:55 135阅读 0赞

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

解题思路:

最长回文字串问题:

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <string.h>
    using namespace std;
    const int MANX = 1010;
    string input;
    int sdp[MANX][MANX];
    int main() {
    	getline(cin, input);
    	int len = input.length();
    	memset(sdp, 0, sizeof(sdp));
    	int ans = 1;
    	for (int i = 0; i < len; ++i) {
    		sdp[i][i] = 1;
    		if (i < len - 1) {
    			if (input[i] == input[i + 1]) {
    				sdp[i][i + 1] = 1;
    				ans = 2;
    			}
    		}
    	}
    	//状态转移
    	for (int i = 3; i <= len; ++i) {
    		for (int j = 0; j + i - 1 < len; ++j) {
    			int k = j + i - 1;
    			if (input[j] == input[k] && sdp[j + 1][k - 1] == 1) {
    				sdp[j][k] = 1;
    				ans = i;
    			}
    		}
    	}
    	cout << ans << endl;
    
    	system("PAUSE");
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关 1040 Longest Symmetric String（动态规划）

1040 Longest Symmetric String 0、题目 Given a string, you are supposed to output the

左手的ㄟ右手/ 2024年04月08日 13:05/ 0 赞/ 53 阅读

相关最长回文子串

最长回文子串 1、参考资料 https://leetcode-cn.com/problems/longest-palindromic-substring/ htt

╰半夏微凉°/ 2022年12月08日 05:24/ 0 赞/ 249 阅读

相关最长回文子串

/ 最长回文子串输入一个字符串s，请找出s中最长回文子串的长度 dp[i][j]是子串s[i...j]中的最长回文子串的长度 / public clas

清疚/ 2022年10月29日 12:23/ 0 赞/ 262 阅读

相关 0005-Longest Palindromic Substring(最长回文子串)

> 这个系列算是出于个人兴趣开的一个新坑吧，最近看到同学刷LeetCode算法题，就想写写那些可以一行Python代码写出来的题目，因此本专栏的文章的解题方式效率不做保证，只为

比眉伴天荒/ 2022年10月15日 04:57/ 0 赞/ 20 阅读

相关最长回文子串

include <iostream> include <vector> include <string> include <algori

淩亂°似流年/ 2022年06月17日 06:53/ 0 赞/ 312 阅读

相关最长回文子串（Longest Palindromic Substring）

Leetcode 5. Longest Palindromic Substring Description Given a string s, find the longe

红太狼/ 2022年06月09日 04:26/ 0 赞/ 189 阅读

相关 Python实现Pat 1040. Longest Symmetric String (25)

[题目][Link 1] Given a string, you are supposed to output the length of the longest sym

你的名字/ 2022年06月04日 08:39/ 0 赞/ 184 阅读

相关 1040. Longest Symmetric String (25)

Given a string, you are supposed to output the length of the longest symmetric sub-strin

淡淡的烟草味﹌/ 2022年05月31日 10:48/ 0 赞/ 181 阅读

相关 (PAT 1040) Longest Symmetric String (DP-最长回文子串)

Given a string, you are supposed to output the length of the longest symmetric sub-strin

悠悠/ 2022年03月19日 10:55/ 0 赞/ 136 阅读

相关最长回文子串

【题目】给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。输入: “babad” 输出: “bab” 注意: “aba”

骑猪看日落/ 2021年09月21日 05:28/ 0 赞/ 405 阅读