目录
- 前言
- 问题介绍
- 解决方案
- 代码编写
- java语言版本
- c语言版本
- c++语言版本
- 思考感悟
- 写在最后
前言
当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~
问题介绍
原问题
给定一个字符串数组chars，求chars中回文字符串子串的最长长度，
如：
chars = [abc1234321]
结果为7
进阶问题
如果现在只能在chars右边添加字符串，求添加的字符串是什么？
解决方案
原问题：
这里介绍一个Manacher算法：
1、首先由于回文字符串存在奇数长度和偶数长度，这里直接将字符串进行填充#，将其全部变成奇数字符串，如 123，变化后 #1#2#3#,长度从3变成7，偶数12，变化后为#1#2#，长度为5
2、申请四个变量，index为当前能够达到最右边的回文字符串的中轴，pR为index能够达到最右边的数组角标，helparr[i]代表以位置i为中轴的回文字符串的最长半径。count代表help的游标
3、当pr达到末尾的时候就不用算了，后面的元素再长不会超过当前的游标作为中轴时的回文字符串半径
4、当计算到count时，首先计算count是否在边界（count不会在边界之外），如果在边界，直接赋值1，从当前开始往两边计算出以当前位置为轴的最长回文字符串长度
5、如果不在边界，则直接可以参考镜像helparr[index * 2 - count]位置的最长长度，然后继续循环扩大即可
进阶问题
进阶问题稍微修改原问题代码即可，通过原问题代码计算出pr第一次达到右边时的index，此时index的最长回文子串左边能够达到的位置假设为end，那么要添加的字符串就是从end一直到位置0即可
代码编写
java语言版本
原问题：
原问题：
/*** 二轮测试：求字符串中的最长回文字符串长度* @return*/public static int manacherCp1(String str) {if (str == null || str.length() == 0) {return 0;}// 字符串处理char[] charsArr = dealStr2Char(str);int pR = -1;int index = 0;int[] helpArr = new int[charsArr.length];int count = 0;int res = 0;while (pR <= charsArr.length) {helpArr[count] = count < pR-1 ? helpArr[index * 2 - count] : 1;while (count - helpArr[count] >= 0 && count + helpArr[count] < charsArr.length) {if (charsArr[count - helpArr[count]] == charsArr[count + helpArr[count]]) {helpArr[count]++;}else {break;}}if (helpArr[count] + count > pR) {pR = helpArr[count] + count + 1;index = count;}res = Math.max(res, helpArr[count]);count++;}// res需要再处理一下(（2*res - 1 - 1） / 2)return res-1;}/*** 字符串填充* @param str* @return*/private static char[] dealStr2Char(String str) {int length = str.length();char[] res = new char[length * 2 + 1];char[] chars = str.toCharArray();int count = 0;for (; count < length; count++) {res[count * 2] = '#';res[count * 2 + 1] = chars[count];}res[count * 2] = '#';return res;}进阶问题
/*** 进阶问题：只能在右边加字符串的情况下，添加最少的字符串使得整个字符串变成回文字符串* @param str* @return*/public static char[] getShortestChar(String str) {if (str == null || str.length() == 0) {return null;}char[] chars = dealStr2Char(str);int pR = -1;int index = 0;int[] helpArr = new int[chars.length];int count = 0;while (pR < helpArr.length) {helpArr[count] = count < pR - 1 ? helpArr[2 * index - count] : 1;while (count + helpArr[count] < chars.length && count - helpArr[count] >= 0) {if (chars[count + helpArr[count]] == chars[count - helpArr[count]]) {helpArr[count] ++;}else {break;}}if (helpArr[count] + count > pR) {pR = helpArr[count] + count + 1;index = count;}count++;}// pr到达了最终的地方，直接处理当前index所在的位置int end = index + 1 - helpArr[index];char[] res = new char[end];count = end-1;index = 0;while (count >= 0) {if ((count & 1) == 1) {res[index++] = chars[count];}count--;}return res;}public static void main(String[] args) {System.out.println(String.valueOf(getShortestChar("abc1234321")));}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
manacher算法代码很简单，但是分析起来情况还是很多的，有兴趣的同学可以自行分析一下，还有就是时间复杂度是O(N)。
写在最后
本文链接：https://my.lmcjl.com/post/13906.html
4 评论