【回文 马拉车】214. 最短回文串

本文涉及知识点

回文 马拉车

LeetCode214. 最短回文串

给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入:s = “aacecaaa”
输出:“aaacecaaa”
示例 2:
输入:s = “abcd”
输出:“dcbabcd”

提示:
0 <= s.length <= 5 * 104
s 仅由小写英文字母组成

回文

n = s.length
将定在s前面增加了n1个字符,则增加的是字符串一定是s,长度为n1的后缀逆序。此时字符串是回文说明:s[0…n-n1-1]是回文。
此问题 ⟺ \iff 求s的最长回文前缀。
先用马拉车算法计算,奇数长度回文的最大半长,看能否包括s[0],如果包括更新最大长度。
偶数长度回文类似。

代码

核心代码

//马拉车计算回文回文
class CPalindrome
{
public:void  CalCenterHalfLen(const string& s){vector<char> v = { '*' };for (const auto& ch : s){v.emplace_back(ch);v.emplace_back('*');}const int len = v.size();vector<int> vHalfLen(len);int center = -1, r = -1;//center是对称中心,r是其右边界(闭)for (int i = 0; i < len; i++){int tmp = 1;if (i <= r){int pre = center - (i - center);tmp = min(vHalfLen[pre], r - i + 1);}for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);vHalfLen[i] = --tmp;const int iNewR = i + tmp - 1;if (iNewR > r){r = iNewR;center = i;}}m_vOddCenterHalfLen.resize(s.length());m_vEvenCenterHalfLen.resize(s.length());for (int i = 1; i < len; i++){const int center = (i - 1) / 2;const int iHalfLen = vHalfLen[i] / 2;if (i & 1){//原字符串奇数长度m_vOddCenterHalfLen[center] = iHalfLen;}else{m_vEvenCenterHalfLen[center] = iHalfLen;}}}vector<int> m_vOddCenterHalfLen, m_vEvenCenterHalfLen;//vOddHalfLen[i]表示 以s[i]为中心,且长度为奇数的最长回文的半长,包括s[i]//比如:"aba" vOddHalfLen[1]为2 "abba" vEvenHalfLen[1]为2
};template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{*seft = max(*seft, other);
}class Solution {
public:string shortestPalindrome(string s) {if ("" == s) { return ""; };CPalindrome pn;pn.CalCenterHalfLen(s);int iMaxR = 0;for (int i = 0; i < s.length(); i++) {int left = i - pn.m_vOddCenterHalfLen[i] + 1;int r = i + pn.m_vOddCenterHalfLen[i] - 1;if (0 == left) {MaxSelf(&iMaxR, r);}}for (int i = 0; i < s.length(); i++) {int left = i - pn.m_vEvenCenterHalfLen[i] + 1;int r = i + pn.m_vEvenCenterHalfLen[i] ;if (0 == left) {MaxSelf(&iMaxR, r);}}string s2 = s.substr(iMaxR + 1);return string(s2.rbegin(), s2.rend()) + s;}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1 , t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());	for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{string s;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){s = "aacecaaa";auto res = Solution().shortestPalindrome(s);AssertEx(string("aaacecaaa"), res);}TEST_METHOD(TestMethod1){s =  "abcd";auto res = Solution().shortestPalindrome(s);AssertEx(string("dcbabcd"), res);}TEST_METHOD(TestMethod2){s = "ab";auto res = Solution().shortestPalindrome(s);AssertEx(string("bab"), res);}TEST_METHOD(TestMethod3){s = "aab";auto res = Solution().shortestPalindrome(s);AssertEx(string("baab"), res);}TEST_METHOD(TestMethod4){s = "";auto res = Solution().shortestPalindrome(s);AssertEx(string(""), res);}};
}

扩展阅读

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

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

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

相关文章

超详解——Python 字典详解——小白篇

目录 1. 创建字典 示例&#xff1a; 2. 访问字典中的元素 示例&#xff1a; 3. 修改字典元素 示例&#xff1a; 4. 删除字典元素 示例&#xff1a; 5. 查找元素是否是字典的键 示例&#xff1a; 6. 标准类型操作符 获取字典长度 合并两个字典 7. 常用内置函数 k…

【Qt】QT textBrowser 设置字体颜色和大小

1. 效果 2. 代码 {ui->methodText->append("<font size9 colorgreen> dddddddddd </font>");ui->methodText->append("<font size9 colorred> vvvvvvvvvv </font>"); }

读AI新生:破解人机共存密码笔记02进化

1. 人工智能的标准模型 1.1. 机器优化人类提供的固定目标 1.1.1. 是一条死胡同 1.1.1.1. 当你走进死胡同时&#xff0c;你最好掉头返回&#xff0c;找出走错的地方 1.2. 问题不在于我们可能无法做好构建人工智能系统的工作&…

atmega8 上传程序

使用icsp 烧写时先关闭串口程序&#xff0c;与串口uart连接相关的电路勿于电脑连接 接触不良 1.使用icsp 上传 1&#xff09;可以直接上传程序 如官方示例blink 或是 serial示例 2&#xff09;可以先烧录bootload 方便下次使用串口上传程序代码 A)使用专门的icsp 上传器上传…

AI Stable diffusion 报错:稳定扩散模型加载失败,退出

可能是内存不够&#xff0c;看看你最近是加了新的大的模型&#xff0c;可以把你的stable-diffusion-webui\models\Stable-diffusion目录下的某个ckpt删除掉&#xff0c;可能ckpt太大&#xff0c;无法加载成功&#xff1b; Stable diffusion model failed to load, exiting 如图…

如何在WIndows虚拟机安装 macOS 黑苹果系统?

在本教程中&#xff0c;我们将介绍如何在虚拟机上安装 macOS 黑苹果系统。黑苹果系统是非苹果公司官方支持的 macOS 系统的非官方版本&#xff0c;可以在普通 PC 上运行。请注意&#xff0c;安装黑苹果系统可能违反苹果的许可协议&#xff0c;请自行承担风险。参考视频教程&…

如何应对生活中的不确定性:仁者安仁,知者利仁。

有较高自尊水平的人&#xff0c;接近于孔子说的&#xff1a;仁者。 ——— 有着稳定的高自尊&#xff0c;无论外在环境如何变化&#xff0c;对其影响都不大&#xff0c;他能够愉快地生活。 相反&#xff1a;一个人处于低自尊状态&#xff0c;就会活得很痛苦&#xff0c;对自己…

手机丢失不惊慌,华为手机已升级至楼层级设备查找!

出门总是丢三落四&#xff0c;手机丢了怎么办&#xff1f;不要怕&#xff0c;只要你的华为手机升级至云空间新版本&#xff0c;就可以进行楼层级设备查找&#xff0c;现在可以查看到具体的楼层了&#xff01; 之前有手机丢失过的朋友&#xff0c;肯定有相似的经历&#xff0c…

Python **运算符(python**kwargs:参数解包)(kwargs:keyword arguments)

文章目录 Python中的 ** 运算符&#xff1a;参数解包参数解包基础语法和示例 在函数定义中使用 **示例代码 使用场景和好处1. 灵活性&#xff1a;使用 **kwargs 允许函数设计得更加灵活&#xff0c;可以接受未来可能增加的新参数而无需修改函数定义。2. 可读性和可维护性&#…

注册中心理论学习

注册中心介绍 注册中心&#xff08;也称为服务注册中心或服务发现服务&#xff09;是微服务架构中的一个关键组件&#xff0c;它负责服务的注册与发现。在微服务体系中&#xff0c;服务实例的数量和位置是动态变化的&#xff0c;注册中心提供了一个集中的地方来存储这些信息&a…

Elasticsearch搜索引擎(高级篇)

3.1 查询语法 | 《ElasticSearch入门到实战》电子书 (chaosopen.cn) day09-Elasticsearch02 - 飞书云文档 (feishu.cn) 目录 第一章 DSL查询 1.1 基本语法 1.2 叶子查询 全文检索查询 精确查询 1.3 复合查询 算分函数查询 bool查询 1.4 排序 1.5 分页 基础分页 深度分…

监控异地组网的方法?

监控异地组网是一项关键的技术&#xff0c;能够实现远程连接和访问。在复杂的网络环境中&#xff0c;使用传统的方法可能会遭遇网络限制和访问速度较慢的问题。而采用新兴的监控异地组网方法&#xff0c;如【天联】组网技术&#xff0c;可以克服这些问题并提供更好的用户体验。…

Linux-笔记 samba实现映射网络驱动器到Win 10

前言 之前通过网上的方法成功映射后&#xff0c;现如今在自己电脑想实现映射服务器共享文件夹到Win 10端发现对之前的方法没有总结导致细节出问题&#xff0c;特此写下笔记。 场景 在服务器编译好代码生成镜像后&#xff0c;在Win10端采用软件烧写镜像&#xff0c;但是镜像在服…

【设计文档】软件项目详细设计说明书案例(套用模板Word)

1引言 1.1编写目的 1.2项目背景 1.3参考材料 2系统总体设计 2.1整体架构 2.2整体功能架构 2.3整体技术架构 2.4设计目标 2.5.1总体原则 2.5.2实用性和先进性 2.5.3标准化、开放性、兼容性 2.5.4高可靠性、稳定性 2.5.5易用性 2.5.6灵活性和可扩展性 2.5.7经济性和投资保护 3系统…

正解 x86 Linux 内存管理

1&#xff0c;机器解析的思路 发现网络上大量的教程&#xff0c;多是以讹传讹地讲解 Linux 内存管理&#xff1b; 都是在讲&#xff1a; 逻辑地址 -> 线性地址 -> 物理地址 这个转换关系是怎么发生的。 上面这个过程确实是程序运行时地址的翻译顺序&#xff1b; …

pytest中失败用例重跑

pip install pytest-rerunfailures 下载rerunfailures插件包 配置文件中加入命令 --reruns 次数 也可在命令行中pytest --rerun-failures2 可以在allure报告中看到重试效果

聊天页面样式

聊天页面样式 代码&#xff1a; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><link rel"styleshee…

如何区分人工智能生成的图像与真实照片(上)

随着最先进扩散模型&#xff08;如Midjourney、Stable Diffusion和Firefly&#xff09;生成的图像具有高度的逼真度&#xff0c;未经训练的我们很难区分真实照片和AI生成的图像。为了解决这个问题&#xff0c;这份指南&#xff0c;帮助读者培养更批判的眼光&#xff0c;识别AI生…

vue-loader

Vue Loader 是一个 webpack 的 loader&#xff0c;它允许你以一种名为单文件组件 (SFCs)的格式撰写 Vue 组件 起步 安装 npm install vue --save npm install webpack webpack-cli style-loader css-loader html-webpack-plugin vue-loader vue-template-compiler webpack…

Android入门第68天-自动更新/升级怎么做(生产级实例)

开篇 今天我们进入第68讲。 在第60天左右其实很多同学们已经进入了APP应用开发了,因为60天内容足以让大家踏上正实的Android开发生涯。 随着开发的深入,我们发觉日常工作中无非就是一些组件的嵌套、合理应用。当代码迭代、功能迭代越来越频繁后我们面临着另一个问题,即:…