核心解决的是字符串中寻找最长回文问题
package com.ncst.improve.one; /** * @author i * @create 2020/7/1 16:57 * @Description 字符串最长回文问题 */ public class Code_04_Manacher { //为字符串前后添加一个 # A#B#A public static char [] manacherString(String str){ char[] chars = str.toCharArray(); char [] res = new char [str.length()*2+1]; int index = 0; for (int i = 0; i != res.length ; i++) { res[i] = (res[i]&1) == 0 ? '#' : chars[index++]; } return res; } public static int maxLcpsLength(String str){ if (str == null || str.length() == 0){ return -1; } char [] chars = manacherString(str); int [] pArr = new int [chars.length];//回文半径数组 int index = -1; int pR = -1; int max = Integer.MIN_VALUE; //遍历字符串 for (int i = 0; i != chars.length ; i++) { //当前最右边界大于i 回文半径 pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - 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]>pR){ pR = i+pArr[i]; index = i; } max = Math.max(max,pArr[i]); } return max-1; } }