【PTA】最长对称子串

ゞ浴缸里的玫瑰 2023-07-02 11:22 22阅读 0赞

#### 题目重述 ####

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

#### 输入格式： ####

输入在一行中给出长度不超过1000的非空字符串。

#### 输出格式： ####

在一行中输出最长对称子串的长度。

#### 输入样例： ####

Is PAT&TAP symmetric?

#### 输出样例： ####

11

#### C++ AC ####

#include <iostream>
    #include <bits/stdc++.h>
    #define MAX 1010
    using namespace std;
    int dp[MAX][MAX];
    int main()
    {
        
        int ans=1;
        string str="";
        getline(cin,str);
    
        memset(dp,0,sizeof(dp));
        for(int i=0;i<str.length();i++)
        {
        
            dp[i][i]=1;
            if(i<str.length()-1)
            {
        
                if(str[i]==str[i+1])
                {
        
                    dp[i][i+1]=1;
                    ans=2;
                }
    
            }
        }
        for(int L=3;L<=str.length();L++)
        {
        
            for(int i=0;i+L-1<str.length();i++)
            {
        
                int j=i+L-1;
                if(str[i]==str[j]&&dp[i+1][j-1]==1)
                {
        
                    dp[i][j]=1;
                    ans=L;
                }
            }
        }
        cout << ans << endl;
        return 0;
    }

#### 参考 ####

胡凡《算法笔记》

发表评论取消回复

表情：

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

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

相关阅读

相关【PTA】最长对称子串

题目重述对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11

ゞ浴缸里的玫瑰/ 2023年07月02日 11:22/ 0 赞/ 23 阅读

相关最长公共子串

题目： [\[编程题\]最长公共子串][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_

男娘i/ 2022年12月07日 15:23/ 0 赞/ 199 阅读

相关最长公共子串与最长连续子串算法

利用DP思想最长公共子串中result\[i\]\[j\]存放str1前i个与result\[j\]个的最长公共子串，当str1\[i + 1\]==str2\[j + 1

男娘i/ 2022年08月11日 16:44/ 0 赞/ 242 阅读

相关最长对称子串——暴力枚举+注意细节

5-12 最长对称子串 (25分) 对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP

男娘i/ 2022年07月12日 10:45/ 0 赞/ 186 阅读

相关最长对称子串——暴力枚举+注意细节

5-12 最长对称子串 (25分) 对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP

柔情只为你懂/ 2022年07月12日 10:45/ 0 赞/ 199 阅读

相关最长对称子串

最长对称子串：给出一个字符串，求出它的最长的对称的子串的长度 \include<iostream> \include<cstdio> \include<algorit

秒速五厘米/ 2022年06月17日 13:59/ 0 赞/ 205 阅读

相关 L2-008 最长对称子串（最长回文串）

L2-008. 最长对称子串时间限制 100 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard

雨点打透心脏的1/2处/ 2022年06月12日 12:25/ 0 赞/ 179 阅读

相关 L2-008. 最长对称子串

L2-008. 最长对称子串时间限制 100 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者陈越

ゝ一纸荒年。/ 2022年05月30日 00:37/ 0 赞/ 184 阅读

相关 L2-008 最长对称子串（25 分）

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定"Is PAT&TAPsymmetric?"，最长对称子串为"s PAT&TAP s"，于是你应该输出11。输入

淡淡的烟草味﹌/ 2022年05月24日 02:04/ 0 赞/ 168 阅读

相关 7-1 最长对称子串（25 分）

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定`Is PAT&TAP symmetric?`，最长对称子串为`s PAT&TAP s`，于是你应该输出11。

╰+哭是因爲堅強的太久メ/ 2022年05月05日 10:28/ 0 赞/ 170 阅读