当前位置：首页 > news >正文

LeetCode 5 -- 区间DP | 中心拓展算法

news 来源：原创 2025/9/6 9:47:23

题目描述

最长回文子串
数据规模为 5e5，必须 manacher 算法

1. DP

由于 $re v erse ()$ 的时间复杂度是 $O (N)$ ，因此暴力肯定是不行的。

$d p$ 的思路：如果 $s [l .. r]$ 是一个回文串，那么我们可以立马得知 $s [l - 1, ..., r + 1]$ 是否是回文串。

也就是说我们可以由小区间得到大区间。

典型的区间 $d p$ 啊。

时间复杂度 $O(N^2)$

2. 中心拓展算法

我们可以枚举字符串的每个点为中心，从这个点开始向两头拓展，如果拓展之后的两头边界仍然相同，说明是回文串，否则结束拓展。

因为如果当前不是回文串，继续拓展下去的话肯定仍然不是。

时间复杂度为 $O(N^2)$

虽然和 $d p$ 的时间复杂度级别是相同的，但是该算法的常数更小，每次拓展是拓展两个元素，而 $d p$ 每次是一个元素。

另外，中心拓展算法无法直接解决字符串长度为偶数的情况，例如 $abba$ ，任意选取一个中心拓展的话，长度都是 $1$ ，因此在中心拓展算法中，我们除了每次选取一个点作为中心外，还要选取两个相邻的点(前提是这两个点的值相同)作为中心处理回文串长度为偶数的情况。

3. Manacher 算法

ref first
ref second

时间复杂度 $O (N)$

我们知道，中心拓展算法是基于暴力匹配的，并且它还不能直接处理偶数长度串。而马拉车算法能有效解决这两个问题，虽然它也是基于暴力匹配，但是它通过预处理做了优化，并且能避免偶数长度回文串的问题。其做法和中心拓展类似，不过它通过使用之前的信息来加速计算。所以，它仍然需要枚举每一个中心。

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;// Malacher's algorithm
int maxLcsplength(string str) 
{// 空字符串直接返回0if (str.length() == 0) return 0;/*========================*//*  一、字符串manacher化  *//*========================*/// 记录下manacher字符串的长度，方便后面使用// 因为我们需要处理偶数的情况，所以长度为n+(n+1)// 例如 aba -> #a#b#a#int len = (int)(str.length() * 2 + 1);// 开辟动态数组chaArr记录manacher化的字符串// 开辟动态数组pArr记录每个位置的回文半径char *chaArr = new char[len];int *pArr = new int[len];// 填充字符串int index = 0;for (int i = 0; i < len;i++) chaArr[i] = (i & 1) ? str[index++] : '#';/*============*//*  二、计算  *//*============*/// R是最右回文边界，C是R对应的最左回文中心，maxn是记录的最大回文半径int R = -1;int C = -1;int maxn = 0;//开始从左到右遍历for (int i = 0; i < len; i++) {// 第一步直接取得可能的"最短"的回文半径// 当i>R时，最短的回文半径是1// 反之，最短的回文半径可能是i对应的i'的回文半径或者i到R的距离pArr[i] = R > i ? min(R - i, pArr[2 * C - i]) : 1; // L=2*C-1//取最小值后开始从边界暴力匹配，匹配失败就直接退出while (i + pArr[i] < len && i - pArr[i] > -1) {if (chaArr[i + pArr[i]] == chaArr[i - pArr[i]]) pArr[i]++;else break;}//观察此时R和C是否能够更新if (i + pArr[i] > R) {R = i + pArr[i];C = i;}//更新最大回文半径的值maxn = max(maxn, pArr[i]);}//记得清空动态数组哦delete[] chaArr;delete[] pArr;// 这里解释一下为什么返回值是maxn-1// 因为manacherstring的长度和原字符串不同// 所以这里得到的最大回文半径其实是原字符串的最大回文子串长度加1// 例如aba,化为#a#b#a#,得到半径为length(b#a#)为4// 但实际结果为length(aba)3return maxn - 1;
}
int main()
{string s1;cin >> s1;cout << maxLcsplength(s1) << endl;return 0;
}

简洁一些的版本

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;int malacher(string str)
{// 特殊判断if(str.empty()) return 0;// 由于需要在头和尾以及每两个字符之间添加特殊符号// 所以需要修改 len 为 len + (len - 1)/*当然也可以不在头和尾添加，只需要每两个字符之间添加即可* 此时，修改 len = str.size() * 2 - 1* 并且将填充字符的逻辑改为：charArr[i] = (i & 1) == 0 ? '#' : str[idx ++ ];*/int len = str.size() << 1 | 1;// 开辟新字符串和回文半径数组// 回文半径：cbabc 的回文半径为 abcchar *chaArr = new char[len];int *pArr = new int[len];// 填充新字符串int idx = 0;for(int i = 0; i < len; i ++ )chaArr[i] = (i & 1) ? str[idx ++ ] : '#';// 计算int R = -1; // 最大回文串的右端点int C = -1; // 最大回文半径的中心int maxn = 0;/* |     |     |     |     |     | *//* |  L  |  i' |  C  |  i  |  R  | *//* |     |     |     |     |     | */for(int i = 0; i < len; i ++ ){// 加速计算：O(1) 时间内求的最短的回文半径pArr[i] = R > i ? min(R - i, pArr[2 * C - i]) : 1; // L=2*C-1// 暴力匹配while(i + pArr[i] < len && i - pArr[i] > -1){if(chaArr[i + pArr[i]] == chaArr[i - pArr[i]])pArr[i] ++ ;else    break;}// 更新if(i + pArr[i] > R){R = i + pArr[i];C = i;}maxn = max(maxn, pArr[i]);}delete[] chaArr;delete[] pArr;return maxn - 1;
}int main()
{string s;   cin >> s;cout << malacher(s) << endl;return 0;
}

LeetCode 5 -- 区间DP | 中心拓展算法

题目描述最长回文子串数据规模为 5e5，必须 manacher 算法 1. DP 由于 r e v e r s e ( ) reverse() reverse() 的时间复杂度是 O ( N ) O(N) O(N)，因此暴力肯定是不行的。 d p dp dp 的思路：如果 s [ l . . r ] s[l..r] s[l..r] 是一个…...

编程日记 2025/9/6 9:47:23

IntelliJ IDEA中Spring Boot 3.4.x+集成Redis 7.x：最新配置与实战指南

‌前言 Spring Boot 3.4.x作为当前‌最新稳定版本‌，全面支持Java 17与Jakarta EE 10规范。本文以‌Spring Boot 3.4.1‌和‌Redis 7.x‌为例，详解如何在IDEA中快速接入Redis，涵盖‌最新依赖配置‌、‌数据序列化优化‌、‌缓存注解‌及‌高…...

编程日记 2025/9/6 9:42:17

数仓建模中计算累计销量

在数仓建模中计算累计销量，通常需要结合时间维度和业务逻辑设计合理的模型与计算逻辑。以下是分步骤的实现思路和示例： 1. 模型设计累计销量的计算通常基于星型模型或雪花模型，核心结构包括： 事实表：记录每一笔销售…...

编程日记 2025/9/6 9:39:44

(多看) CExercise_05_1函数_1.2计算base的exponent次幂

题目： 键盘录入两个整数：底(base)和幂指数(exponent)，计算base的exponent次幂，并打印输出对应的结果。（注意底和幂指数都可能是负数） 提示：求幂运算时，基础的思路就是先无脑把指数转…...

编程日记 2025/9/3 1:05:59

Pollard‘s Rho 算法

Pollard’s Rho 算法：一场数学与计算机科学的巧妙结合在现代计算机科学中，素数分解、整数因子化问题有着广泛的应用，尤其是在密码学领域。然而，当面对一个大合数时，寻找其因子仍然是一个非常复杂的问题。我们常常依赖…...

编程日记 2025/9/5 4:02:21

8款分形长虹玻璃科幻渐变海报设计JPG背景素材 The Gradient Backgrounds Pack

天空从未如此美好 — 直到有人将日落洒在您的屏幕上。这些渐变是带有心跳的液体颜色，从熔化的金色转变为深紫色，就像地平线一样。 8 个背景中的每一个都以 45003000 像素和 300dpi 的速度脉冲，清晰到足以让您感觉自己可以直接踏入光芒中。但这…...

编程日记 2025/9/5 19:41:52

AIGC9——AIGC时代的用户体验革命：智能交互与隐私保护的平衡术

引言：当AI成为交互主角 2024年，淘宝AI客服"阿里小蜜"日均处理20亿次咨询，日本虚拟偶像"初音未来"演唱会门票3秒售罄——这些现象标志着AIGC已深度融入人机交互场景。但与此同时，过度个性化的推荐引发"信…...

编程日记 2025/9/5 1:02:45

vm虚拟机虚拟出网卡并ping通外网

在 Linux 和 Windows 系统中，即使不使用网络命名空间（namespace），也能实现虚拟网卡上网。以下是不同场景下的实现方法： 一、Linux 系统（不使用网络命名空间） 1. 直接创建虚拟网卡对&#xff08…...

编程日记 2025/9/2 8:23:28

基于时间卷积网络TCN实现电力负荷多变量时序预测(PyTorch版)

前言系列专栏:【深度学习：算法项目实战】✨︎ 涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域，讨论了各种复杂的深度神经网络思想，如卷积神经网络、循环神经网络、生成对…...

编程日记 2025/9/3 18:10:56

ESXi8的部署过程

目录一、系统安装二、ESXI8的序列号三、挂载硬盘和新建VMFS数据分区四、通过数据存储浏览器上传下载文件五、Windows远程桌面端口隐射六、导出虚机一、系统安装 1、使用UtrIOS系统制作ESXI8的启动盘； 2、服务器启动F8按键进入Popup启动选项，选择U盘启动； 3、安…...

编程日记 2025/8/30 18:56:41

IntelliJ IDEA 2020~2024 创建SpringBoot项目编辑报错: 程序包org.springframework.boot不存在

目录前奏解决结尾前奏哈！今天在处理我的SpringBoot项目时，突然遇到了一些让人摸不着头脑的错误提示： java: 程序包org.junit不存在 java: 程序包org.junit.runner不存在 java: 程序包org.springframework.boot.test.context不存在 java:…...

编程日记 2025/9/5 4:27:30

Windows 权限配置文件解析与安全分析（GPP,GPO,LSA）

在 Windows 网络环境中，权限配置文件用于管理用户权限、密码策略和访问控制，涵盖组策略首选项（GPP）、本地安全策略（LSA）、注册表以及 Active Directory 组策略（GPO） 等。这些配置文件…...

编程日记 2025/9/4 14:39:08

【微服务】基础概念

1.什么是微服务微服务其实就是一种架构风格，他提倡我们在开发的时候，一个应用应该是一组小型服务而组成的，每一个服务都运行在自己的进程中，每一个小服务都通过HTTP的方式进行互通。他更加强调服务的彻底拆分。他并不是仅局限于…...

编程日记 2025/8/27 0:59:09

MYOJ_4342:(洛谷P1087)[NOIP 2004 普及组] FBI 树(二叉树实操，递归提高)

题目描述我们可以把由 “0” 和 “1” 组成的字符串分为三类：全 “0” 串称为 B 串，全 “1” 串称为 I 串，既含 “0” 又含 “1” 的串则称为 F 串。 FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三…...

编程日记 2025/8/30 11:54:23

LLM(13)：词编码后的位置

原则上，token 嵌入是大型语言模型（LLM）的合适输入。然而，LLM 的一个小缺点是它们的自注意力机制无法指导序列中 token 的位置或顺序。在前面介绍的嵌入层的工作方式中，无论 token ID 在输入序列中的位置如何&#xff0…...

编程日记 2025/9/3 7:47:16

MINIQMT学习课程Day4

聚宽的模拟/实盘跟单系统，已经全部介绍完毕，上传完毕了，相信大家已经可以进行聚宽的miniqmt的交易了。如果还有疑问，私信我进行沟通。现在开始进入新的课题，如何学习python，我不教那些乱七八糟的&#xff…...

编程日记 2025/9/3 12:04:42

AWS云服务：大数据公司实现技术突破与商业价值的核心引擎

在数据驱动决策的时代，大数据公司面临着海量数据存储、实时计算、复杂分析及安全合规等核心挑战。如何高效构建弹性、可扩展且低成本的技术架构，成为企业能否在竞争中胜出的关键。亚马逊云科技（AWS）作为全球云计算领域的领导者&am…...

编程日记 2025/9/5 22:24:20

Openpyxl使用教程(包含处理大数据量案例)

文章目录一、简介功能特性应用场景使用优势二、常用方法1、工作簿wb2、工作表ws 三、案例1、创建新工作簿2、将Excel数据存入list中3、按行读取文件(适合大文件)4、按指定行读取文件(适合大文件) 一、简介在 Python 数据处理领域，openpyxl 凭借其卓越的功能与易…...

编程日记 2025/9/6 8:29:42

蓝桥杯15届宝石组合

问题描述在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝…...

编程日记 2025/9/1 22:38:20

THE UNIVERSITY OF MANCHESTER-NUMERICAL ANALYSIS 1-3.4数值积分-复合积分公式

3.4.1 复合梯形法则梯形法则仅使用两个点来近似积分，显然对于大多数应用来说，这不足够。为了提高精度，有多种方法可以利用更多的点和函数值。正如我们刚才在Newton-Cotes方法和辛普森法则中所看到的，一种方法是使用更高阶的插值函数。另一种方法是将区间划分为更小的区间…...

编程日记 2025/9/5 22:55:35

嵌入式系统应用-拓展-相关开发软件说明

这里以STM32的系列产品为例子，利用MDK的集成开发平台进行开发过程中，所有相关软件安装说明。 1 集成开发环境安装 1.1 MDK 下载 1.1.1 官网下载官方下载地址： https://www.keil.com/download/product/ 选择MDK-ARM ，填写一些…...

编程日记 2025/9/3 10:42:38

react实现上传图片到阿里云OSS以及问题解决（保姆级）

一、优势提高上传速度：前端直传利用了浏览器与 OSS 之间的直接连接，能够充分利用用户的网络带宽。相比之下，后端传递文件时，文件需要经过后端服务器的中转，可能会受到后端服务器网络环境和处理能力的限制，…...

编程日记 2025/9/4 15:24:15

嵌入式学习笔记——ARM-中断与异常

文章目录中断与异常的区别中断与 DMA 的区别中断能否睡眠？下半部能否睡眠？1. 中断处理程序不能睡眠2. 下半部（SoftIRQ、Tasklet、Workqueue） 中断处理注意点1. 快进快出2. 避免阻塞3. 正确返回值4. 如何处理大量任务5. 避免竞态问…...

编程日记 2025/8/31 20:58:15

OpenHarmony子系统开发 - 安全（十二）

OpenHarmony SELinux开发指导（五） 一、OpenHarmony SELinux常见问题 neverallow编译报错处理现象描述编译SELinux时会进行neverallow检查，当配置的策略不合理时，可能出现违反neverallow编译报错。 neverallow check failed…...

编程日记 2025/9/3 0:43:59

深入解析ARM与RISC-V架构的Bring-up核心流程

深入解析ARM与RISC-V架构的Bring-up核心流程作者：嵌入式架构探索者 | 2023年10月引言在嵌入式开发中，处理器的Bring-up（启动初始化）是系统运行的第一道门槛。ARM和RISC-V作为两大主流架构，其Bring-up流程既有共性…...

编程日记 2025/8/27 15:22:11

挺经典的回溯题的。 class Solution { public:vector<vector<int>> result;void recursion(vector<int>& nums,vector<int>& now){if(nums.size()0){result.push_back(now);return ;}for(int i0;i<nums.size();i){now.push_back(nums[i]);…...

编程日记 2025/9/3 13:16:34

vue中如何动态的绑定图片

在项目中遇到需要动态的改变图片路径，图片路径并非是从后台获取过来的数据。因此在data中必须用require加载，否则会当成字符串来处理。...

编程日记 2025/8/27 14:13:09

湖北师范大学计信学院研究生课程《工程伦理》12.6章节练习

1【单选题】下列哪个不是数字身份的特点？ A. 多样性 B. 唯一性 C. 可变性 D. 允许匿名和假名 2【单选题】下列哪项不是现代国家的基本职能。 A. 保护政权统一 B. 保护本国面对其他国家侵犯 C. 保护国内每个人免受他人侵犯 D. 承担发展国民经济 3【单选题】哪个国家在全球率先发…...

编程日记 2025/9/3 1:33:05

prism WPF 登录对话框登录成功后显示主界面

prism WPF 登录对话框登录成功后显示主界面项目结构 LoginUC.xaml <UserControl x:Class"PrismWpfApp.Views.LoginUC"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml…...

编程日记 2025/9/3 13:05:21

MySQL统计信息

1. 什么是统计信息？ 统计信息就像是数据库的"地图"，它告诉优化器： 每个表有多大（有多少行数据） 每个索引的"区分度"（有多少不同的值） 数据分布情况（哪些值出…...

编程日记 2025/9/4 17:02:17

Spark，配置hadoop集群2

编写Hadoop集群启停脚本 1.建立新文件，编写脚本程序在hadoop101中操作，在/root/bin下新建文件：myhadoop，输入如下内容： 2.分发执行权限保存后退出，然后赋予脚本执行权限 [roothadoop101 ~]$ chmod x /r…...

编程日记 2025/9/2 14:34:55

⭐算法OJ⭐重建行程【哈密尔顿路径】（C++ 实现）Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from “JFK”, thus, t…...

编程日记 2025/9/1 5:37:13

题目描述

1. DP

2. 中心拓展算法

3. Manacher 算法

相关文章：