Java练习—-》求字符串中的最长回文子串

手贱，做了一道对于我来说挺难的题目 嘿嘿！ 挺有意思的，分享一下

文章目录

• 前言
• 一，题目
• 二，思路图形解析
• 代码

前言

第一次把自己的解题思维写出来，可能写的不太好，请给位原谅，哈哈哈哈额，如果有错的，请各位大佬帮我指出来哈，谢谢！！(＾Ｕ＾)ノ~ＹＯ

一，题目

求一串字符串的最长回文子串，这里以cabacabae为例

二，思路图形解析

第一步：观察这串字符串—》

第二步：找出最长回文子串，并设数—》

说明：在这里，假设知道最长回文子串，那这里的resCenter和maxRigth,reslengthgs和maxRight都是固定的了，但是实际上我们不知道，所以这里说它是动态的。 第三步：假设我们不知道最长回文子串的情况下—-》

这里我举了个例子，resCenter是从左到右走的，同样我们可以观察到有对称的j，也就是在一个对称范围内左边和右边是一样的。 所以resCenter有3中情况： 第四步：

在这一步，只是知道resLength的范围内部分，其他不在这范围内的我们不知道，所以只能一步一步对比

第五步：

此时左边的resCenter和j的resLength相等，为1. 第六步：

可以看出此时的resCenter到最左边界的长度为6，设下标为1的元素为x，下标为9的元素为y，此时数组b中的b[x]==b[y],设下表为17的元素为z，那么从上面几种情况判断以及j的位置，有b[x]!= b[z],所以b[y]!=b[z]。

注意：上面图中的resCenter的痕迹和j的痕迹是一致的，我这样比较好看出来两者的对称关系。所以，这里设出来的所有参数的每次移动的位置只有一个，j只是我画比较好理解的，，不要理解错了哈！嘻嘻~~ 你也可以理解为一根绳子，找到对称点，阶段之后，再找对称点，从对称点（每一点都可以理解为对称点）开始，对比对称点前后是否是一样的，一样的则继续，遇到粗细不一样的就停止，这就相当于一个回文，记录下来，然后又继续…直到到最后一个。 所以这里需要重头开始，那时间复杂度就是o（n），空间复杂度就是o（1）。 （不想改图了，那个resLength的长度是动态的，因为在这之前我们是不知道最长回文子串的，但是我们可以假设，上面图没有交代，哈哈哈额）

代码

所以，根据上面的分析，我们如果限定了maxRigth和j的位置，那不就可以分析各种情况了嘛！因为maxRigth和j的范围不同，其他的也会不同，所以有以下代码—-》

重点部分分析：假设我们知道了最长的回文子串，那么resCenter则确定了，resLength也就确定了，同样maxRigth和maxCenter也确定了。那么在没确定之前，我们可以观察到在待定的最长回文子串中，resCenter的变化和j的变化是一样的，那我们可以用j来表示，其实resCenter 向后走的时候，也就是j。所以我们可以在j到maxRigth之内找到其元素的回文。那么在maxRigth之外的，我们有所不知，需要一个一个的去配对，同时在这里我们需要注意数组越界问题，所以要限定边界。在最左边界为j-c[j],肯定要大于等于0；最右边界为j+c[j]【这里的数组c[j]表示的是b[i]为中心的回文子串的半径】，就要小于length，同时因为在整个字符数组都左右的最后一个元素都是“#”，所以最左边界的值和最右边界的值是相等的，这个一定要限定！！。如果右边界越界了，那就更新一下maxRigth和maxCenter就可以了。 写代码的方式有很多种，也可以不这样写 ヽ(￣ω￣(￣ω￣〃)ゝ

应该就这样了吧，不知道有没有表达清楚( ´･･)ﾉ(._.`)，不知道在哪里做动图，额，，你们知道在哪里弄动图的，可以告诉我一声哈，我啥也不会，哈哈哈哈额😂 那就这样吧。。

先不要走哈，留下三连嘛！！嘻嘻

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/181197.html原文链接：https://javaforall.cn