HDU - 3068 最长回文

2023-12-22 08:48
文章标签 最长 回文 hdu 3068

本文主要是介绍HDU - 3068 最长回文，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题面

http://acm.hdu.edu.cn/showproblem.php?pid=3068

2.题意

给你一个字符串，让你求最长回文子串，注意，是最长回文字串，不是最长回文子序列

3.思路

方法有很多，有一个我还不会，这是后缀数组版本的

解法如下，比如原来的字符串为

s = "abab"

则构造数组s + '#' + reverse(s)

也就是下面这样

“abab#baba”

然后，枚举回文串的中心，因为回文串的长度有奇数和偶数两种可能，所以我们要分类讨论。

看到题目中那么多输出中间结果，你也知道这道题我做的有多么痛苦了大哭

后缀数组第一题，Never Stop AC!!

4.代码

/*****************************************************************> File Name: Cpp_Acm.cpp> Author: Uncle_Sugar> Mail: uncle_sugar@qq.com> Created Time: 2016年07月29日 星期五 09时30分02秒
*****************************************************************/
# include <c

这篇关于HDU - 3068 最长回文的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/523319。

相关文章

最长公共子序列问题的深度分析与Java实现方式

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列（LCS）问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动
阅读更多...
关于最长递增子序列问题概述

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法：贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列，例如 nums = [10, 9, 2
阅读更多...
poj3261（可重复k次的最长子串）

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
阅读更多...
csu1328（近似回文串）

csu1328（近似回文串）

题意：求近似回文串的最大长度，串长度为1000。 解题思路：以某点为中心，向左右两边扩展，注意奇偶分开讨论，暴力解即可。时间复杂度O(n^2); 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2093 考试排名（sscanf）

hdu 2093 考试排名（sscanf）

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2