回文串-新华三2023笔试(codefun2000)
创始人
2024-11-15 12:39:57
0

题目链接
回文串-新华三2023笔试(codefun2000)

题目内容

给定一个长度为 n 的字符串,请你找出该字符串中最长的回文子串。
回文子串定义为满足从左往右读和从右往左读相同的字符串。

输入描述

第一行一个整数 n,表示字符串长度。
接下来一行一个长度为 n 的字符串。 1 ≤ n ≤ 1 0 4 1≤n≤10^4 1≤n≤104

输出描述

输出一行一个字符串表示最长的回文子串。

样例1

输入

6
qaqbcd

输出

qaq

提示

本题开启 Special Judge,如有多个答案输出其中一个即可。

题解1

#include using namespace std;  const int N=1e4 + 10; char s[N]; int n, dp[N]; // dp[i]表示以第i个字符结尾,且回文串包含第i个字符的最长回文串的长度   int main(){ 	scanf("%d", &n); 	scanf("%s", s + 1); 	int maxLen = 0, R = 0; // maxLen表示最长回文串的长度,R表示最长回文串的结束位置  	for(int i = 1; i <= n; i++){ 		if(i > 0 && s[i] == s[i - 1 - dp[i - 1]]) dp[i] = dp[i - 1] + 2; 		else dp[i] = 1; 		if(maxLen < dp[i]){ 			maxLen = dp[i]; 			R = i; 		} 	} 	 	for(int i = R - maxLen + 1; i <= R; i++) printf("%c", s[i]); 	printf("\n"); 	return 0; } 

相关内容

热门资讯

透视苹果版!wpk作弊是真的吗... 透视苹果版!wpk作弊是真的吗,wpk德州局透视,2025新版技巧(都是存在有挂);所有人都在同一条...
透视代打!we poker插件... 透视代打!we poker插件,wepoker插件程序激活码(本来是真的有挂)1、完成wepoker...
透视规律!wpk辅助器,wpk... 透视规律!wpk辅助器,wpk透视辅助靠谱吗,透明教程(一贯是真的有挂)1、起透看视 wpk透视辅助...
透视软件!wepoker有没有... 透视软件!wepoker有没有插件,wepoker软件辅助程序(一直是真的有挂);1、金币登录送、破...
透视教学!wpk安卓下载辅助,... 透视教学!wpk安卓下载辅助,wpk官网下载链接,新版2025教程(其实真的是有挂);1、点击下载安...
透视免费!wepoker黑侠辅... 透视免费!wepoker黑侠辅助器,wepoker好友房开挂(竟然存在有挂)1、wepoker好友房...
透视插件!wepoker怎么挂... 透视插件!wepoker怎么挂飞机,wepoker怎么买辅助(原来真的是有挂);1、透视插件!wep...
透视辅助!wpk私人辅助,wp... 透视辅助!wpk私人辅助,wpk控制牌是真的吗,技巧教程(都是是有挂)1、wpk控制牌是真的吗ai机...
透视中牌率!WePOker有没... 透视中牌率!WePOker有没有透视方法,wepoker辅助器激活码(都是有挂)所有人都在同一条线上...
透视计算!wpk作弊,如何判断... 透视计算!wpk作弊,如何判断wpk辅助软件的真假,第三方教程(总是是真的有挂)如何判断wpk辅助软...