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

算法笔记(十二)—— Manacher算法(回文子串)

计算字符串内的最大回文子串,常用的暴力扩散在应对长度为偶数的回文时会遇到一些问题。

Manacher基础:对字符串进行填充,在字符串开头结尾以及字符间填充‘#’,以来应对偶数回文时的问题。(这是采用暴力扩再除2,可以得到正确的结果)

填充的字符不一定需要添加字符串内没有出现的字符

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

Manacher算法 - O(N^2)

概念:

回文直径:每个字符暴力扩的最大回文子串长度

回文半径:回文直径的一半

回文半径数组:将每个字符对应的回文半径信息存储起来

之前所扩的所有位置中所达到的最右边界 init R = -1

C:取最远边界时,中心点在哪

情况处理:

1. 当前来到的点不在右边界内: 暴力扩

2. 当前点在R内,R关于C的对称点L,当前点关于C的对称点i'

2.1 i'的回文区域彻底在[L R]的内部,则当前点的回文半径等于i'的回文半径

2.2 i'的回文区域有一部分在[L R]外,则i的回文半径等于R-i+1

2.3 i'的回文区域压在了[L R]上,i的回文半径从R开始暴力扩计算即可

// Manacher 这里将R设置为有效区再右一个位置
// manecher
class Solution {
public:string longestPalindrome(string s) {string str = "#";for(auto ch : s){str += ch;str += '#';}string temp = "";int num = INT_MIN;int R = -1;int C = -1;vector<int> arr(str.size() , 0);for(int i = 0 ; i<str.size() ; i++){arr[i] = R>i?min(arr[2*C-i] , R-i):1;while(i+arr[i]<str.size() && i-arr[i]>-1){if(str[i+arr[i]]==str[i-arr[i]])++arr[i];else break;}num = max(num , arr[i]);if(num==arr[i])temp = str.substr(i-arr[i]+1 , 2*arr[i]-1);}string res = "";for(auto ch : temp){if(ch!='#'){res += ch;}}return res;}
};

滑动窗口

使用双指针来代表一个当前窗口,左指针和右指针都只能往右滑动(L不能超过R)

1. 准备一个双端队列,存储数组下标,保证队列内数据单调排序

2. 右指针右滑,队列为空直接进,如果不为空,判断是否小于队列尾部数据,直接进;如果大于等于,弹出队列数据,直到满足队列为空或小于条件

3. 左指针右滑,判断队列头部数据对应下标是不是左指针左方的下标,如果是,从头部弹出

单调栈

知道每一个数左边最近的大数和右边最近的大数是谁(无重复数),并且时间复杂度O(N)

1. 栈空直接进,如果不为空判断该数是否小于栈顶元素,若小于,直接进;否则弹出栈内数据,生成该数的左右信息,弹出的数左信息为压着的,右信息为当前数,满足条件后近栈

2.  遍历结束,进入清算阶段,依次出栈并生成信息

如果有重复数据的话,用链表来存放即可,哈希表<链表<下标>,数据值>

相关文章:

算法笔记(十二)—— Manacher算法(回文子串)

计算字符串内的最大回文子串&#xff0c;常用的暴力扩散在应对长度为偶数的回文时会遇到一些问题。 Manacher基础&#xff1a;对字符串进行填充&#xff0c;在字符串开头结尾以及字符间填充‘#’&#xff0c;以来应对偶数回文时的问题。&#xff08;这是采用暴力扩再除2&#x…...

【数据结构】顺序表和链表的区别和联系(详解)

顺序表和链表的区别&#xff08;详解&#xff09; 文章目录顺序表和链表的区别&#xff08;详解&#xff09;前言一、顺序表和链表的关系二、顺序表1.优点2.缺点三、链表1.优点2.缺点四、区别表格总结前言 本文给大家介绍顺序表和链表的各自的优缺点和区别与联系&#xff0c;结…...

【Linux操作系统】【综合实验三 用户帐号、文件系统与系统安全管理】【更新中】

文章目录一、实验目的二、实验要求三、实验内容四、实验报告要求一、实验目的 要求掌握Linux系统用户的创建、删除与管理操作&#xff1b;熟悉Linux文件系统的管理模式&#xff0c;学会创建用户文件系统并装载和卸载文件系统&#xff1b;掌握超级用户的管理方式与权限&#xf…...

华为OD机试真题 用 C++ 实现 - 整数分解 | 多看题,提高通过率

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…...

Java集合(一)---List和set

1.Java集合有哪些&#xff1f;集合类型主要有3种&#xff1a;set(集&#xff09;、list(列表&#xff09;和map(映射)Map接口和Collection接口是所有集合框架的父接口&#xff1a;1. Collection接口的子接口包括&#xff1a;Set接口和List接口2. Map接口的实现类主要有&#xf…...

手撸一个Table组件(Table组件不过如此)

一、前言 手写Table组件这个文章我一直都想写&#xff0c;今天终于得空来写它了。小编认为Table组件是组件库里"较为复杂"的一个组件&#xff0c;因为它的扩展性非常强&#xff0c;并且它的基础样式如何去写都非常考究&#xff0c;那么今天我就带大家来实现一个基础…...

Python|Leetcode刷题日寄Part01

Python|Leetcode刷题日寄Part0101&#xff1a;两数之和02&#xff1a;无重复字符的最长子串03&#xff1a;两数相加04&#xff1a;反转链表05&#xff1a;有效的括号06&#xff1a;回文数07&#xff1a;删除有序数组中的重复项08&#xff1a;删除链表的倒数第N个结点09&#xf…...

微信小程序更改头像昵称

背景 前面写了一篇关于小程序头像昵称获取更改的方案&#xff0c;有很多小伙伴私信我发一个整体的逻辑思路&#xff01; 解决思路 前面的这篇文章中我们给出了页面中获取头像昵称的代码&#xff1a; <view class"headInfo" data-weui-theme"{{theme}}&qu…...

Linux 基础知识之文件系统

目录一、文件系统1.文件种类2.Linux和Windows文件后缀的不同3.查看文件类型3.绝对路径与相对路径二、系统分区三、目录结构一、文件系统 1.文件种类 Linux中一切皆文件。目光所及&#xff0c;皆是文件。文件的种类共有七种&#xff0c;每种文件都有自己的独特标识&#xff1a;…...

LeetCode 36. 有效的数独

LeetCode 36. 有效的数独 难度&#xff1a;middle\color{orange}{middle}middle 题目描述 请你判断一个 9x99 x 99x9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1−91-91−9 在每一行只能出现一次。数字 1−91-91−9 在每一列…...

2023-02-22 cascades-columbia-核心处理记录

摘要: columbia是哥伦比亚对于cascades的一个改进, 并且paper写的也相对详尽. 虽然cacades的实现有很多,比较出名的就是greenplum的gporca, 不过columbia也有其显著的优点. 本文通过对columbia的分析展开对cascades优化器思想的探讨. 参考: 2023-02-10 哥伦比亚cascades-xu-…...

华为分布式存储(FusionStorage)

Server SAN SAN&#xff1a;存储区域网络 IP SAN&#xff1a;以太网交换机和普通网线连接的存储&#xff0c;交换机之间做堆叠FC SAN&#xff1a;FC&#xff08;光纤&#xff09;交换机和光纤连接的存储&#xff0c;交换机之间做级联Server SAN&#xff1a;可以使用以太网交换机…...

说说 React 中 fiber、DOM、ReactElement、实例对象之间的引用关系

原生组件 fiber 原生组件 fiber&#xff0c;指的就是 type 为 “span”、“div” 的 fiber。 1.fiber.stateNode 指向真实 DOM 节点&#xff1b;2.node["__reactFiber$" randomKey] 指向对应 fiber&#xff0c;使用随机数是防止和业务代码的属性名冲突&#xff0c;…...

LaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式)

文章目录 LaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式)refnotedemoLaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式) ref markdown中公式编辑教程 在 Microsoft Word 中使用 LaTeX 输入数学公式【比较全,介绍了支持的语法和不支持的语法】 用wo…...

S5P6818_系统篇(2)源码编译及烧录

源码获取 源码获取和操作流程 1.下载liunux下的系统制作脚本&#xff0c;可以烧录系统和构建镜像 git clone https://github.com/friendlyarm/sd-fuse_s5p6818.git 如果出现git错误可使用如下方法&#xff1a; git config --global http.sslverify false 2.阅读该工具rea…...

LDPC码的编译码原理简述

关于fpga调用ldpc IP core的相关参数问题可以看我的另一篇文章 LDPC码由Gallager在1962年提出&#xff0c;全称为 Low Density Parity-check Codes 低密度奇偶校验码 它的译码性能可以逼近Shannon信道容量限&#xff0c;广富盛名的Turbo码也被证明是LDPC码的一个特例。并且LDPC…...

网络安全——数链路层据安全协议

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​​ 目录 前言 一.数据链路层安全协议简介 1.数据链路安全性 二.局域网数据链路层协议 1.…...

spring的启动过程(一) :IOC容器的启动过程

一、web容器的加载 首先我们要先知道一个web项目的启动过程。 将Web项目部署到Tomcat中的方法之一&#xff0c;是部署没有封装到WAR文件中的Web项目。要使用这一方法部署未打包的webapp目录&#xff0c;只要把我们的项目&#xff08;编译好的发布项目&#xff0c;非开发项目&am…...

这次,我的CentOS又ping不通www.baidu.com了(gateway配置)

当我们保证了宿主机与虚拟机的ip地址在同一网段&#xff0c;并且我们使用虚拟机ping宿主机&#xff0c;与宿主机ping虚拟机都可以互相ping通的情况下虚拟机却ping不通外网了&#xff0c;由于涉及到了跨越网络访问&#xff0c;所以我们应该把问题聚焦在网关的配置上&#xff01;…...

启智社区“我为开源狂”第六期活动小白教程之基础活跃榜

一、写在前面 春天来啦~启智社区第六期活动也来啦&#xff01; 有奖金的哦~~ 基础活跃榜奖金根据用户活跃程度进行100-300元的激励。 挑战升级榜需要用户完成相应任务&#xff0c;达标者可获得300-1000元的激励。 邀请助力榜根据用户邀请情况进行积分累加&#xff0c;按实际达…...

从Stable Diffusion到DiT:为什么说Transformer是扩散模型的下一站?

从Stable Diffusion到DiT&#xff1a;Transformer如何重塑扩散模型的未来 在图像生成领域&#xff0c;扩散模型正经历着从U-Net架构向Transformer架构的范式转移。这一转变不仅仅是技术组件的简单替换&#xff0c;而是代表着生成式AI在可扩展性、训练效率和模型容量方面的重大突…...

别光看手册!手把手教你读懂气体放电管(GDT)的6个关键参数,选型不踩坑

气体放电管实战选型指南&#xff1a;从参数表到电路设计的6个关键决策点 每次打开气体放电管&#xff08;GDT&#xff09;的英文数据手册&#xff0c;面对密密麻麻的参数表格和波形图&#xff0c;不少工程师都会陷入选择困难——这些数值到底如何影响实际电路保护效果&#xf…...

医用超声图像干扰伪像算法:原理、识别与抑制技术综述

引言 医用超声成像因其无创、实时、低成本等优点,已成为临床诊断不可或缺的工具。然而,超声图像质量极易受到各种物理因素和系统限制的影响,从而产生干扰伪像。这些伪像并非真实的解剖结构,而是由声波传播特性、设备硬件、操作手法等因素导致的虚假或失真的图像信息。准确…...

别再硬啃C++了!用这个UE插件,5分钟让Web页面跑在虚幻引擎里

零代码整合Web与虚幻引擎&#xff1a;用WebUI插件打造数字孪生控制面板当Three.js的数据可视化大屏需要与UE5的工业场景联动&#xff0c;或是Vue构建的管理后台要嵌入数字孪生项目时&#xff0c;传统方案往往要求开发者同时精通前端框架和虚幻引擎蓝图系统。现在&#xff0c;通…...

别再死记硬背了!用UE5动画蓝图状态机做个“开关门”交互,5分钟搞懂运行流

用UE5动画蓝图状态机实现智能门交互&#xff1a;从理论到实战第一次接触虚幻引擎的动画系统时&#xff0c;那些抽象的概念总让人望而生畏。记得我刚开始学习UE4时&#xff0c;光是理解"状态机"这个概念就花了整整一周时间——直到我亲手实现了一个会自动开关的门。这…...

破局奈奎斯特:从同步采样时序抖动到全链路EMC,高精度采集卡的超频设计边界

http://www.z-linear.com 在数据采集卡&#xff08;DAQ&#xff09;的选型手册中&#xff0c;工程师们习惯于紧盯“分辨率”和“采样率”这两个显性参数。然而&#xff0c;当面对极其苛刻的工业应用——例如多轴伺服电机的闭环控制、电网电能质量的高次谐波分析、或微弱生物电…...

显示what failed:VMMR0.r0--已解决

VirtualBox版本5.2.44 win11家庭中文版 以下是已经尝试内核隔离无用的情况下&#xff0c;所写出的解决方案。 winR&#xff0c;输入services.msc 禁用该服务后 管理员身份打开cmd&#xff0c;输入bcdedit /set hypervisorlaunchtype off 重启后确认查看方式 ①管理员身…...

神经模拟器超越训练数据:从误差纠正到高效科学计算

1. 项目概述&#xff1a;当神经模拟器“青出于蓝”在科学计算这个行当里&#xff0c;求解偏微分方程&#xff08;PDE&#xff09;是模拟从流体流动到热量传递、从电磁场到量子力学等几乎所有物理现象的基础。我们这些搞计算的人&#xff0c;常年跟有限差分、有限体积、有限元这…...

告别卡顿!用IL2CPP优化你的Unity游戏:性能提升与包体瘦身实测

告别卡顿&#xff01;用IL2CPP优化你的Unity游戏&#xff1a;性能提升与包体瘦身实测最近在优化一款Unity游戏时&#xff0c;我发现了一个令人头疼的问题&#xff1a;游戏在低端设备上频繁卡顿&#xff0c;包体大小也超出了预期。经过一番探索&#xff0c;我决定尝试将脚本后端…...

Houdini刚体破碎VAT导出到UE5:从静态碎片到动态 Niagara 粒子群的实战转换

Houdini刚体破碎VAT导出到UE5&#xff1a;从静态碎片到动态 Niagara 粒子群的实战转换在影视级实时特效制作中&#xff0c;大规模刚体破碎效果一直是个技术难点。传统方法需要消耗大量计算资源来处理每个碎片的物理模拟&#xff0c;而Vertex Animation Texture&#xff08;VAT&…...