题目：求最长回文串并求出回文串

曾经终败给现在 2024-03-26 23:42 57阅读 0赞

### 动态规划 ###

![64cf9cbd849d41a59cdcb89fa7741a97.png][]

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e4 + 10;
    string s;
    int dp[N][N];
    int main()
    {
    	cin >> s;
    	int n = s.size();
    	for(int i = 0; i < n; i ++)
    	{
    		dp[i][i] = 1;//长度为1的字符串都是回文串	
    	}
    	int maxlen = 1;//记录最长回文串 
    	int start;
    	for(int len = 2; len <= n; len ++)//枚举回文串长度 
    	{
    		for(int left = 0; left + len - 1 < n; left ++)//枚举左端点 
    		{
    			int right = left + len - 1;//枚举右端点 
    			if(s[left] != s[right])//左右两边不一样一定不是回文串
    			{
    				dp[left][right] = 0;	
    			}
    			else//左右两边一样，说明当前字符串是否是回文串取决于[left + 1...right - 1]区间的字符串是否是回文串 
    			{
    				if(len == 2)dp[left][right] = 1;
    				else
    				{
    					dp[left][right] = dp[left + 1][right - 1];	
    				} 
    			}
    			if(len > maxlen)
    			{
    				if(dp[left][right] == 1)
    				{
    					maxlen = len;
    					start = left;
    				}
    			}
    		}	
    	} 
    	cout << maxlen;
    	string t = "";
    	for(int i = start; i < start + maxlen; i ++)t += s[i];
    	cout << t;
    	return 0;
    }

[64cf9cbd849d41a59cdcb89fa7741a97.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/da0ae2221b344af1a3c38010d0b98184.png

发表评论取消回复

表情：

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

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

相关阅读

相关题目：求最长回文串并求出回文串

动态规划 ![64cf9cbd849d41a59cdcb89fa7741a97.png][] include<bits/stdc++.h> using

曾经终败给现在/ 2024年03月26日 23:42/ 0 赞/ 58 阅读

相关最长回文子串

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

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

相关最长回文子串

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

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

相关求最长回文串

一、题目给定一个字符串 s，找到 s 中最长的回文子串二、动态规划解法 public String longestPalindrome(String

向右看齐/ 2022年10月10日 01:37/ 0 赞/ 146 阅读

相关【动态规划】求最长公共子串，最长回文子串

题目 : 给定两个字符串，求出它们之间连续的最长的相同子字符串的长度。 eg : fbaabe，ebaabf，连续最长子串长度为4。注意：求最长回文子串也可以用求最长公

朴灿烈づ我的快乐病毒、/ 2022年08月09日 00:59/ 0 赞/ 258 阅读

相关最长回文子串

回文串指给定的字符串，正着读和反着读都是一样的。如ADA，反过来还是ADA即为回文串。最长回文子串指查找一给定字符串中最长的回文串。通常有以下4种解法。主要考虑的是时间复杂

雨点打透心脏的1/2处/ 2022年08月07日 04:43/ 0 赞/ 264 阅读

相关最长回文子串

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

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

相关最长回文串

public String longestPalindrome(String s) { int start = 0, end = 0;

刺骨的言语ヽ痛彻心扉/ 2022年06月10日 10:22/ 0 赞/ 183 阅读

相关 python 最长回文串

from collections import Counter class Solution : """ @param s: a

Love The Way You Lie/ 2022年05月21日 02:52/ 0 赞/ 206 阅读

相关最长回文子串

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

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