回文串-新华三2023笔试(codefun2000)

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

题目内容

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

输入描述

第一行一个整数 n，表示字符串长度。
接下来一行一个长度为 n 的字符串。$1\le n\le 10^4$

输出描述

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

样例1

输入

6
qaqbcd

输出

qaq

提示

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

题解1

#include<bits/stdc++.h> 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; }