马拉车算法
Manacher算法 ,用于处理最长回文字符串的问题,可以在O(n)的情况下,求出一个字符串的最长回文字符串
回文串的基础解法:
以每个点为中心对称点,看左右两边的点是否相同。这种算法的时间复杂度为O(n^2),并且奇偶字符串的中心点是不同的。因此在处理时,可以在字符串的中间加上特殊字符,以使其都变成奇字符串,列如字符串:abba可以变成:#a#b#b#a#,字符串aba可以变成:#a#b#a#这样无论对于奇字符串还是偶字符串都变成同样的处理逻辑了。具体实现代码如下所示:
data = "#"+"#".join(data)+"#"
n = len(data)
res = 0
for i in range(1,n-1):temp = 0l = i-1r = i+1while l>0 and r<n:if data[l] == data[r]:temp += 1l-=1r+=1else:res = max(res,temp)breakres = max(res,temp)
print(res)
马拉车算法
马拉车算法同样使用特殊字符做预处理。首先先讲解一下马拉车算法的原理。对于字符串bcbabcc来说,通过处理可以将其变成 ^#b#c#b#a#b#c#c#$
我们使用一个数组p来记录每个字符的可以扩展长度。比如第一个字符c来说,以c为中心点,分别判断其左边的字符和右边的字符是否相等,看以c为中心点的最长回文字符串是3。即p[4]=3。
接下来,我们用c,r 两个字符来分别表示中心点和可扩展到最右边的长度。当我们以c为中心点时,其c为4,r为7。
根据回文字符串的特性来说,回文字符串的左边必定是等于右边的。因此以c为中心左边的三个字符的p值一定是等于以c为中心右边三个字符的p值的。
从1开始遍历字符串,初始化c=0,r=0,p=[0]*字符串长度,
有三种情况:
1、遍历的下标大于r:此时前面回文字符串的特性不能用,因此需要找到以该下标为中心点,向左向右判定p[i]的值
2、遍历的下标小于r:根据回文字符串的特性,可以直接填充,比如·当我们遍历到底一个字符c时,前面p的值为0,0,1,0,3.此时中心值为4,r为7,则由回文字符串的特性可以直接将后面的三个进行对称填充为010。另一点需要注意的是,不能单纯的进行对称填充还要考虑范围。如果对称的值大于可覆盖的范围是不可取的。
具体的python实现代码为:
def manacher(li):n = '^#' + '#'.join(li) + '#$'c = 0r = 0p = [0] * len(n)for i in range(1, len(n) - 1):##在边界内if i <= r:p[i] = min(p[2 * c - i], r - i)##判断左右是否相等while n[i - (1 + p[i])] == n[i + (1 + p[i])]:p[i] += 1##超出边界,重新定义边界和中心点if p[i] + i > r:r = p[i] + ic = ireturn max(p)
li = input()
print(manacher(li))
参考文章:
彻底搞懂马拉车(Manacher)
参考视频:
b站马拉车算法
相关文章:
马拉车算法
Manacher算法 ,用于处理最长回文字符串的问题,可以在O(n)的情况下,求出一个字符串的最长回文字符串 回文串的基础解法: 以每个点为中心对称点,看左右两边的点是否相同。这种算法的时间复杂度为O࿰…...
Debezium同步之如何同步GIS数据
Debezium 可以用于同步数据库中的变更数据(CDC),包括GIS(地理信息系统)数据。GIS 数据通常存储在具有地理空间数据类型的表中,例如 PostGIS(PostgreSQL 的扩展)中的 geometry 或 geography 类型。通过 Debezium,可以实时捕获和同步这类数据的变更。本文章简单介绍Post…...
自动化之ansible(二)
一、ansible中playbook(剧本) 官方文档: Ansible playbooks — Ansible Community Documentation 1、playbook的基本结构 一个基本的playbook由以下几个主要部分组成 hosts: 定义要执行任务的主机组或主机。 become: 是否需要使用超级用户…...
Docker+Dify部署DeepSeek-r1本地知识库
安装配置Docker Desktop 软件下载 Docker Desktop版本:4.38.0.181591 Docker Desktop下载地址:Docker: Accelerated Container Application Development 或者从这里下载:DockerDesktop-4.38.0.181591资源-CSDN文库 点击图下所示位置,下载windows-AMD64版本软件 启用Hy…...
C#基础:使用Linq进行简单去重处理(DinstinctBy/反射)
目录 一、示例代码 二、示例输出 三、注意雷点 四、全字段去重封装方法 1.封装 2.示例 一、示例代码 using System; using System.Collections.Generic; using System.Linq;public class Program {public static void Main(){// 创建一些示例实体对象var people new Li…...
HTML5 面试题
1. HTML5 新增了哪些重要特性? 语义化标签:这些标签有助于提高页面的可读性和可维护性。多媒体支持:HTML5 引入了 和 标签,可以直接嵌入音频和视频文件,无需依赖插件。本地存储:引入了 localStorage 和 se…...
【C++】优先级队列宝藏岛
> 🍃 本系列为初阶C的内容,如果感兴趣,欢迎订阅🚩 > 🎊个人主页:[小编的个人主页])小编的个人主页 > 🎀 🎉欢迎大家点赞👍收藏⭐文章 > ✌️ 🤞 …...
开关电源实战(一)宽范围DC降压模块MP4560
系列文章目录 文章目录 系列文章目录MP4560MP4560 3.8V 至 55V 的宽输入范围可满足各种降压应用 MOSFET只有250mΩ 输出可调0.8V-52V SW:需要低VF肖特基二极管接地,而且要靠近引脚,高压侧开关的输出。 EN:输入使能,拉低到阈值以下关闭芯片,拉高或浮空启动 COMP:Compens…...
Git是什么
简单介绍: Git是一个分布式版本控制系统,用于跟踪文件的更改,特别是在多人协作开发的环境中。 Key: 分布式 版本控制 系统 最常用于软件开发,但也可以用于管理任何类型的文件和文件夹。 Git帮助团队跟踪和管理文件的历史版本&a…...
双非计科毕业,二战未果想就业,选择嵌入式开发还是Java开发更合适?
今天给大家分享的是一位粉丝的提问,双非计科毕业,二战未果想就业,选择嵌入式开发还是Java开发更合适? 接下来把粉丝的具体提问和我的回复分享给大家,希望也能给一些类似情况的小伙伴一些启发和帮助。 同学提问&#x…...
性格测评小程序开发指南
目录 前言目录01 需求分析02 数据源设计03 搭建用户管理04 题库管理05 用户注册06 用户注册校验07 用户登录08 测评功能搭建09 提交结果10 生成报告 学习目标面向人群结语 前言 欢迎阅读《性格测评小程序开发指南》!本书旨在为开发者、低代码爱好者和学习者提供一个…...
shell编程总结
前言 shell编程学习总结,1万3千多字带你学习shell编程 往期推荐 14wpoc,nuclei全家桶:nuclei模版管理工具Nuclei 哥斯拉二开,免杀绕过规避流量检测设备 fscan全家桶:FscanPlus,fs,fscan适用…...
析言GBI:用自然语言交互重构企业数据分析范式
亲爱的小伙伴们😘,在求知的漫漫旅途中,若你对深度学习的奥秘、Java 与 Python 的奇妙世界,亦或是读研论文的撰写攻略有所探寻🧐,那不妨给我一个小小的关注吧🥰。我会精心筹备,在未来…...
【论文技巧】Mermaid VSCode插件制作流程图保存方法
插流程图快点 利用Mermaid Preview插件自带功能 如果你的VSCode安装了支持导出图片的Mermaid预览插件(如 Mermaid Markdown Syntax Highlighting 等),可以按以下步骤进行: 打开Mermaid代码文件:在VSCode中打开包含M…...
Unity 位图字体
下载Bitmap Font Generator BMFont - AngelCode.com 解压后不用安装直接双击使用 提前设置 1、设置Bit depth为32 Options->Export options 2、清空所选字符 因为我们将在后边导入需要的字符。 Edit->Select all chars 先选择所有字符 Edit->Clear all chars i…...
科技快讯 | DeepSeek推出NSA加速长上下文训练,xAI Grok系列将陆续开源,月之暗面发布Kimi Latest新模型
阶跃星辰首次开源Step系列多模态大模型 2月18日,财联社消息,阶跃星辰与吉利汽车集团宣布,双方合作开发的阶跃Step系列多模态大模型向全球开发者开源。包括参数量达300亿的Step-Video-T2V视频生成模型和行业内首款产品级开源语音交互大模型Ste…...
网络安全 | 5G网络安全:未来无线通信的风险与对策
网络安全 | 5G网络安全:未来无线通信的风险与对策 一、前言二、5G 网络的技术特点2.1 超高速率与低延迟2.2 大容量连接与网络切片三、5G 网络面临的安全风险3.1 网络架构安全风险3.2 设备终端安全风险3.3 应用场景安全风险3.4 用户隐私安全风险四、5G 网络安全对策4.1 强化网络…...
Linux 实操篇 组管理和权限管理、定时任务调度、Linux磁盘分区和挂载
一、组管理和权限管理 (1)Linux组基本介绍 在linux中的每个用户必须属于一个组,不能独立于组外 在linux中每个文件有所有者、所在组、其他组的概念 (2)文件/目录 所有者 一般为文件的创建者,谁创建了该…...
应用案例 | uaGate SI助力汽车零部件工厂将生产数据传输到MES
一、背景和挑战 (图1 汽车零部件工厂生产车间) 随着汽车工业的不断发展,新能源汽车市场的竞争日益激烈,这对汽车零部件供应商提出了更高的要求,包括提升产品精度、增强可靠性、节能环保以及控制成本等多个方面。某国际…...
Android JNI的理解与使用。
写在前面:Java相对于C/C来说是更高级的语言,隐藏了指针,可读性更高,更容易学习,但是无法直接操作硬件、运行速度较慢也是不可回避的硬伤。JNI就是Java官方定义的一套标准“接口”,用于Java和C/C之间互相调用…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
一些实用的chrome扩展0x01
简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序,无论是测试应用程序、搜寻漏洞还是收集情报,它们都能提升工作流程。 FoxyProxy 代理管理工具,此扩展简化了使用代理(如 Burp…...
