Manacher算法(求最长回文字符串长度)

本文主要是介绍Manacher算法(求最长回文字符串长度)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这里写图片描述

//
public class StringProblem{//Manacher算法 预处理public static char[] manacherString(String str) {char[] charArr = str.toCharArray();char[] res = new char[str.length() * 2 + 1];int index = 0;for (int i = 0; i != res.length; i++) {res[i] = (i & 1) == 0 ? '#' : charArr[index++];}return res;}//Manacher算法 O(N)复杂度求最长回文子串public static int maxLcpsLength(String str) {if (str == null || str.length() == 0) {return 0;}char[] charArr = manacherString(str);int[] pArr = new int[charArr.length];int index = -1;int pR = -1;int max = Integer.MIN_VALUE;for (int i = 0; i != charArr.length; i++) {pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {if (charArr[i + pArr[i]] == charArr[i - pArr[i]])pArr[i]++;else {break;}}if (i + pArr[i] > pR) {pR = i + pArr[i];index = i;}max = Math.max(max, pArr[i]);}return max - 1;}//添加最短字符串构成回文串，求添加的最短字符串public static String shortestEnd(String str) {if (str == null || str.length() == 0) {return null;}char[] charArr = manacherString(str);int[] pArr = new int[charArr.length];int index = -1;int pR = -1;int maxContainsEnd = -1;for (int i = 0; i != charArr.length; i++) {pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {if (charArr[i + pArr[i]] == charArr[i - pArr[i]])pArr[i]++;else {break;}}if (i + pArr[i] > pR) {pR = i + pArr[i];index = i;}if (pR == charArr.length) {maxContainsEnd = pArr[i];break;}}char[] res = new char[str.length() - maxContainsEnd + 1];for (int i = 0; i < res.length; i++) {res[res.length - 1 - i] = charArr[i * 2 + 1];}return String.valueOf(res);}public static void main(String[]args){//System.out.println("Hello");String str1 = "abc1234321ab";System.out.println(maxLcpsLength(str1)); //最长回文串的长度String str2 = "abcd123321";System.out.println(shortestEnd(str2));  //返回添加的获得最短字符串}}