字符串后面补最短长度的字符,使其整体成回文字符串(java)

news/2024/3/28 21:57:04/文章来源:https://blog.csdn.net/SP_1024/article/details/131739715

回文字符串算法

  • 补齐字符串使其成为回文字符串
    • Manacher 算法
    • 代码演示
  • Manacher 算法

补齐字符串使其成为回文字符串

给定一个字符串str,只能在str的后面添加字符,想让str整体变成回文串,返回至少要添加几个字符

Manacher 算法

首先介绍下manacher 算法:
Manacher 算法是一种线性时间复杂度的求解最长回文子串的算法。它的核心思想是利用已知回文信息,避免重复计算。 Manacher 算法的基本思想是通过预处理得到一个包含原字符串所有回文子串的数组,然后对于每个字符,如果它是回文中心,则将它的位置加倍,否则不做任何修改。最后返回数组中最大的值即可 。具体可以看下上期manacher算法。
Manacher算法 – 回文长度算法
可以先看上期的回文字符串的算法,这个可以在时间复杂度为O(n)的情况下,计算出最长回文子串的长度。

在这个题中,我们只需要找到第一次半径到字符串末尾的字符位置,然后补齐前面到半径位置的字符,就是需要的最短的字符串。
举个例子:
123abcbabc 在这个字符串中,用manacher 算法中,找到第一次回文半径到字符末尾的位置字符,也就是倒数一个a的位置,然后补齐以a为只心的回文字符前面的字符,也就是ba321.使其整体成为回文字符串。

代码演示

/*** 补齐字符串。* @param s* @return*/public static String shortestEnd(String s) {//只有一个字符串时,不需要补if (s == null || s.length() < 2){return null;}char[] chars = manacherString(s);int[] pArr = new int[chars.length];int C = 0;int R = 0;int maxContainsEnd = -1;for (int i = 0;i < chars.length;i++){pArr[i] = R > i ? Math.min(pArr[2 * C - i],R - i) : 1;while (i + pArr[i] < chars.length && i - pArr[i] > -1){if (chars[i + pArr[i]] == chars[i - pArr[i]]){pArr[i]++;}else {break;}}if (i + pArr[i] > R){R = i + pArr[i];C = i;}if (R == chars.length){maxContainsEnd = pArr[i];break;}}char[] ans = new char[s.length() - maxContainsEnd + 1];for (int i = 0; i < ans.length;i++){ans[ans.length - i -1] = chars[i * 2 + 1];}return new String(ans);}/*** 处理字符串* @param s* @return*/public static char[] manacherString(String s){char[] chars = s.toCharArray();char[] res = new char[chars.length * 2 + 1];int index = 0;for (int i = 0; i < res.length;i++){res[i] = (i & 1) == 0 ? '#' : chars[index++];}return res;}

Manacher 算法

Manacher算法 – 回文长度算法

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_331320.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Midjourney助力交互设计师设计网站主页

Midjourney的一大核心优势是提供创意设计&#xff0c;这个功能也可以用在网站主页设计上&#xff0c;使用Midjourney prompt 应尽量简单&#xff0c;只需要以"web design for..." or "modern web design for..."开头即可 比如设计一个通用SAAS服务的初创企…

阿里云AliYun物联网平台使用-客户端API获取设备传感数据

一、前言 上一篇文章中&#xff0c;已经实现了虚拟数据上云&#xff0c;本文我们将进行上位机客户端的开发&#xff0c;即通过调用阿里云IOT物联网云平台的SDK&#xff0c;开发能获取传感器的遥感数据。 二、云平台操作 调用API需要用户的AccessKey Secret&#xff0c;这意味着…

因创始人被捕,Multichain停运!华人加密项目信任何在?

Multichain作为第四大加密货币桥梁&#xff0c;允许用户在八个区块链之间转移加密货币&#xff0c;并持有近16亿美元的投资者存款。对于运行在Fantom区块链上的DeFi而言&#xff0c;多链极为重要。 然而&#xff0c;跨链协议MultiChain5月下旬爆出“出金延迟或暂停”的灾情&…

产业大模型刚开卷,京东跑进“最后半公里”

点击关注 文&#xff5c;姚 悦 编&#xff5c;王一粟 “京东一直在探索哪些产品、技术、场景可以真正把大模型用起来&#xff0c;在我们内部的场景中反复验证后&#xff0c;才决定在7月份对外发布&#xff0c;现在我们在零售、健康、物流、金融等业务场景里已经积累了一些经…

Java使用JNI实现C文件的调用

1.使用IDEA新建工程 构建最基本的maven类型就行&#xff0c;文件结构如下&#xff1a; 其中最主要的类如下&#xff1a; package org.linx;public class TestJNI {static {/*** 加载jni库&#xff0c;有一个重要的点就是生成的为libnative.so&#xff0c;下面加载代码需要消…

【Maven三】——maven生命周期和插件

系列文章目录 Maven之POM介绍 maven命令上传jar包到nexus 【Maven二】——maven仓库 maven生命周期和插件 系列文章目录前言一、什么是生命周期&why1.三套生命周期2.clean生命周期3.default生命周期4.site生命周期5.命令行与生命周期 二、插件目标三、插件绑定1.内置绑定2…

将媒体公司资产迁移到 Amazon S3 的技术方案

随着媒体公司的发展&#xff0c;他们在仓库中积累了大量的旧磁带和未数字化的视频。这些资产可能很有价值&#xff0c;但以目前的形式很难访问和货币化。此外&#xff0c;将这些资产存储在仓库中既有风险又昂贵。 媒体企业可以通过将其资产迁移到云存储来解决这些问题&#xf…

【C++】面试基础搬运

c/c c三大特性 封装 最开始接触代码是C语言&#xff0c;那么开始写一些逻辑代码的时候会很麻烦&#xff0c;因为你要在函数中定义变量&#xff0c;然后按顺序写对应的逻辑&#xff0c;接着可以将逻辑封装成函数。当时会感觉很麻烦&#xff0c;因为很散装&#xff0c;知道后面…

Nacos报错Could not resolve placeholder ‘order.name‘ in value “${order.name}“怎么解决?

出现这个原因有两个&#xff1a; 1.首先在Nacos配置中心&#xff0c;写入yml配置文件的数据和后端服务在取数据的时候名称不一致 如下图&#xff0c;现在我的配置中心为order-service 看看其中的文件内容信息&#xff1a; 再看看后端是怎么取的&#xff1a; 看出上面错误了吗…

C# IEnumerator 用法

一、概述 IEnumerator 是所有非泛型枚举器的基接口。 其泛型等效项是 System.Collections.Generic.IEnumerator<T> 接口。 C# 语言的 foreach 语句&#xff08;在 Visual Basic 中为 for each&#xff09;隐藏了枚举数的复杂性。 因此&#xff0c;建议使用 foreach 而不…

[每周一更]-(第54期):Go的多版本管理工具

参考 https://zhuanlan.zhihu.com/p/611253641https://learnku.com/articles/78326 前文概要 Go语言从开始使用从1.13起步&#xff0c;随着泛型的支持&#xff0c;带领团队在转型Go的时候&#xff0c;做基础组件架构选型使用1.18&#xff0c;但是Go版本不断迭代想使用最新版本…

3Ds max入门教程:创建尼亚加拉大瀑布模型

推荐&#xff1a; NSDT场景编辑器助你快速搭建可二次开发的3D应用场景 初学者在3ds Max中为尼亚加拉大瀑布建模 这次您将学习通过几个简单的步骤在3ds max中对尼亚加拉大瀑布&#xff08;从远处看起来很逼真&#xff09;进行建模。所以&#xff0c;让我们开始吧&#xff01; …

Flutter:EasyLoading(loading加载、消息提示)

前言 官方虽然提供了内置的加载指示器和提示信息&#xff0c;但是功能比较简陋&#xff0c;这里推荐&#xff1a;flutter_easyloading CircularProgressIndicator CircularProgressIndicator()加粗样式 ScaffoldMessenger.of(context).showSnackBar(const SnackBar(// 提示…

怎么用电脑做动图?常见动图的制作方法

常见的gif图片有两种&#xff0c;一种是通过gif合成功能制作&#xff0c;另一种是由视频转gif动图&#xff0c;那么对于日常不是专业设计出身的小伙伴&#xff0c;该使用什么样的gif制作功能&#xff0c;能够满足两种动图制作呢&#xff1f;下面这款gif制作器&#xff08;https…

UE4 常用控制台命令

ue4执行控制台命令有两种方式&#xff0c;一是在运行时按~呼出控制台输入命令后回车执行&#xff0c;二是调用蓝图函数ExecuteConsoleCommand函数传入参数执行命令&#xff0c;需要注意shipping包无法执行控制台命令 常用命令&#xff1a; Stat FPS 显示帧率 Stat Slate 显示…

快速而简单的视频格式转换方法

在数字时代&#xff0c;我们经常需要将视频文件从一种格式转换为另一种格式。无论是因为兼容性问题&#xff0c;还是为了在特定设备上播放视频&#xff0c;视频格式转换是一项非常常见的任务。本文将介绍视频格式转换的基本知识和步骤。 首先&#xff0c;了解不同的视频格式非常…

【数据结构】之红黑树

红黑树 红黑树的概念红黑树的性质红黑树的插入操作&#xff08;核心&#xff09;情况一&#xff1a;uncle存在且为红情况二&#xff1a;uncle不存在/存在且为黑&#xff08;在同一侧&#xff09;情况三&#xff1a;uncle不存在/存在且为黑&#xff08;在两侧&#xff09;总结 红…

03插值与拟合

9.已知飞机下轮廓线上数据如下&#xff0c;分别用分段线性插值和三次样条插值求x每改变0.1时的y值。 x035791112131415y01.21.72.02.12.01.81.21.01.6 %9.已知飞机下轮廓线上数据如下&#xff0c;分别用分段线性插值和三次样条插值求每改变0.1时的y值。x [0 3 5 7 9 11 12 1…

简单工厂模式详解

文章目录 前言一、简单工厂模式定义二、举个例子三、简单工厂模式的缺点总结 前言 本篇我们了解一下简单工厂模式&#xff0c;它是设计模式的雏形&#xff0c;是学习设计模式的开端&#xff0c;我会结合案例说明它的设计思路。 一、简单工厂模式定义 简单工厂模式并不是GoF23…

【运维工程师学习五】数据库之MariaDB

【运维工程师学习五】数据库 1、常用的关系型数据库2、C/S结构3、MariaDB图形客户端4、安装MariaDB5、启动MariaDB及验证启动是否成功6、验证启动——端口7、验证启动——进程8、MariaDB配置文件路径主配置文件解读&#xff1a; 9、MariaDB的配置选项10、MariaDB客户端连接1、在…