目录
一.KMP算法解决的问题
二.Manacher算法解决的问题
基本概念
优化
一.KMP算法解决的问题
暴力求解复杂度O(N*M)
next数组：next[i]表示arr[0...i-1]的前缀和后缀的最长公共长度。
Y位置失败，将前缀和后缀完全匹配，将前缀的部分和后缀对齐，然后比较str2新位置值和str1当前位置x是否匹配。如果失败。。。周而复始，直到最后0位置匹配都失败，那么str1位置往后移动一位，str2从0位置开始。
public static int getIndexOf(String s, String m) {if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {return -1;}char[] str1 = s.toCharArray();char[] str2 = m.toCharArray();int i1 = 0;int i2 = 0;int[] next = getNextArray(str2); //O(M)//O(N)while (i1 < str1.length && i2 < str2.length) {if (str1[i1] == str2[i2]) {i1++;i2++;} else if (next[i2] == -1) { //都来到了0位置都配不出来 str1换个开头吧i1++;} else { //str2还能往前跳 i2 = next[i2];}}// i1 或者 i2 越界了return i2 == str2.length ? i1 - i2 : -1;}public static int[] getNextArray(char[] ms) {if (ms.length == 1) {return new int[] { -1 };}int[] next = new int[ms.length];next[0] = -1;next[1] = 0;int i = 2; //next数组int cn = 0;while (i < next.length) {if (ms[i - 1] == ms[cn]) {next[i++] = ++cn;} // 当前跳到cn位置的字符，和i-1位置的字符失配else if (cn > 0) {cn = next[cn];} // cn配到第一个位置，都不能匹配上，说明前后缀没有公共部分else {next[i++] = 0;}}return next;}public static void main(String[] args) {String str = "abcabcababaccc";String match = "ababa";System.out.println(getIndexOf(str, match));}
二.Manacher算法解决的问题
一般做法：我用每个位置为中心向左右两边扩，一定可以找到最长回文子串吗？ 不能
回文串长度为偶数的情况被省略了。。。（长度为偶数的回文，轴其实在虚位置）
为了既找到长度为奇数和偶数的回文，可以在字符串头尾、每两个字符之间加上同一个特字符。这个特殊字符其实不要求是原串中没出现的。
基本概念
回文半径长度 = 回文长度 / 2
原串回文长度 = 回文半径长度-1
回文半径数组 => 在遍历的过程中需要将每个位置为中心的最长回文长度记下来
最长回文有边界R， 最长回文中心C
优化
代码中的回文有边界优点小改动，是最长回文长度右端的下一个位置。
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;}public static int maxLcpsLength(String str) {if (str == null || str.length() == 0) {return 0;}char[] charArr = manacherString(str); //1221 -> #1#2#2#1#int[] pArr = new int[charArr.length]; // 回文半径数组int C = -1; //中心int R = -1; //回文右边界的再往右一个位置 最右的有效区是R-1位置int max = Integer.MIN_VALUE; //扩出来的最大值for (int i = 0; i != charArr.length; i++) { // 每一个为位置都求回文半径// i至少的回文区域，先给pArr[i]pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - 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] > R) {R = i + pArr[i];C = i;}max = Math.max(max, pArr[i]);}return max - 1;}public static void main(String[] args) {String str1 = "abc1234321ab";System.out.println(maxLcpsLength(str1));}