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

马拉车算法

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算法 ,用于处理最长回文字符串的问题&#xff0c;可以在O&#xff08;n&#xff09;的情况下&#xff0c;求出一个字符串的最长回文字符串 回文串的基础解法&#xff1a; 以每个点为中心对称点&#xff0c;看左右两边的点是否相同。这种算法的时间复杂度为O&#xff0…...

Debezium同步之如何同步GIS数据

Debezium 可以用于同步数据库中的变更数据(CDC),包括GIS(地理信息系统)数据。GIS 数据通常存储在具有地理空间数据类型的表中,例如 PostGIS(PostgreSQL 的扩展)中的 geometry 或 geography 类型。通过 Debezium,可以实时捕获和同步这类数据的变更。本文章简单介绍Post…...

自动化之ansible(二)

一、ansible中playbook&#xff08;剧本&#xff09; 官方文档&#xff1a; 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 新增了哪些重要特性&#xff1f; 语义化标签&#xff1a;这些标签有助于提高页面的可读性和可维护性。多媒体支持&#xff1a;HTML5 引入了 和 标签&#xff0c;可以直接嵌入音频和视频文件&#xff0c;无需依赖插件。本地存储&#xff1a;引入了 localStorage 和 se…...

【C++】优先级队列宝藏岛

> &#x1f343; 本系列为初阶C的内容&#xff0c;如果感兴趣&#xff0c;欢迎订阅&#x1f6a9; > &#x1f38a;个人主页:[小编的个人主页])小编的个人主页 > &#x1f380; &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐文章 > ✌️ &#x1f91e; &#x1…...

开关电源实战(一)宽范围DC降压模块MP4560

系列文章目录 文章目录 系列文章目录MP4560MP4560 3.8V 至 55V 的宽输入范围可满足各种降压应用 MOSFET只有250mΩ 输出可调0.8V-52V SW:需要低VF肖特基二极管接地,而且要靠近引脚,高压侧开关的输出。 EN:输入使能,拉低到阈值以下关闭芯片,拉高或浮空启动 COMP:Compens…...

Git是什么

简单介绍&#xff1a; Git是一个分布式版本控制系统&#xff0c;用于跟踪文件的更改&#xff0c;特别是在多人协作开发的环境中。 Key: 分布式 版本控制 系统 最常用于软件开发&#xff0c;但也可以用于管理任何类型的文件和文件夹。 Git帮助团队跟踪和管理文件的历史版本&a…...

双非计科毕业,二战未果想就业,选择嵌入式开发还是Java开发更合适?

今天给大家分享的是一位粉丝的提问&#xff0c;双非计科毕业&#xff0c;二战未果想就业&#xff0c;选择嵌入式开发还是Java开发更合适&#xff1f; 接下来把粉丝的具体提问和我的回复分享给大家&#xff0c;希望也能给一些类似情况的小伙伴一些启发和帮助。 同学提问&#x…...

性格测评小程序开发指南

目录 前言目录01 需求分析02 数据源设计03 搭建用户管理04 题库管理05 用户注册06 用户注册校验07 用户登录08 测评功能搭建09 提交结果10 生成报告 学习目标面向人群结语 前言 欢迎阅读《性格测评小程序开发指南》&#xff01;本书旨在为开发者、低代码爱好者和学习者提供一个…...

shell编程总结

前言 shell编程学习总结&#xff0c;1万3千多字带你学习shell编程 往期推荐 14wpoc&#xff0c;nuclei全家桶&#xff1a;nuclei模版管理工具Nuclei 哥斯拉二开&#xff0c;免杀绕过规避流量检测设备 fscan全家桶&#xff1a;FscanPlus&#xff0c;fs&#xff0c;fscan适用…...

析言GBI:用自然语言交互重构企业数据分析范式

亲爱的小伙伴们&#x1f618;&#xff0c;在求知的漫漫旅途中&#xff0c;若你对深度学习的奥秘、Java 与 Python 的奇妙世界&#xff0c;亦或是读研论文的撰写攻略有所探寻&#x1f9d0;&#xff0c;那不妨给我一个小小的关注吧&#x1f970;。我会精心筹备&#xff0c;在未来…...

【论文技巧】Mermaid VSCode插件制作流程图保存方法

插流程图快点 利用Mermaid Preview插件自带功能 如果你的VSCode安装了支持导出图片的Mermaid预览插件&#xff08;如 Mermaid Markdown Syntax Highlighting 等&#xff09;&#xff0c;可以按以下步骤进行&#xff1a; 打开Mermaid代码文件&#xff1a;在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日&#xff0c;财联社消息&#xff0c;阶跃星辰与吉利汽车集团宣布&#xff0c;双方合作开发的阶跃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磁盘分区和挂载

一、组管理和权限管理 &#xff08;1&#xff09;Linux组基本介绍 在linux中的每个用户必须属于一个组&#xff0c;不能独立于组外 在linux中每个文件有所有者、所在组、其他组的概念 &#xff08;2&#xff09;文件/目录 所有者 一般为文件的创建者&#xff0c;谁创建了该…...

应用案例 | uaGate SI助力汽车零部件工厂将生产数据传输到MES

一、背景和挑战 &#xff08;图1 汽车零部件工厂生产车间&#xff09; 随着汽车工业的不断发展&#xff0c;新能源汽车市场的竞争日益激烈&#xff0c;这对汽车零部件供应商提出了更高的要求&#xff0c;包括提升产品精度、增强可靠性、节能环保以及控制成本等多个方面。某国际…...

Android JNI的理解与使用。

写在前面&#xff1a;Java相对于C/C来说是更高级的语言&#xff0c;隐藏了指针&#xff0c;可读性更高&#xff0c;更容易学习&#xff0c;但是无法直接操作硬件、运行速度较慢也是不可回避的硬伤。JNI就是Java官方定义的一套标准“接口”&#xff0c;用于Java和C/C之间互相调用…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...