package com.zuoshen.jichutisheng.class03; public class code01 { /** * 字符串匹配算法 * next[k]表示为从0到k-1中最长前缀和后缀的匹配长度 * @param s 文本串,父串 * @param m 模式串,子串 * @return 在父串中查找子串,存在返回父串中子串的起始下标,否则返回-1 */ public static int KMP(String s, String m) { if (s == null || m == null || m.length() < 1 || s.length() < m.length()) { return -1; } char[] chars1 = s.toCharArray(); char[] chars2 = m.toCharArray(); int i1 = 0; int i2 = 0; int[] next = getNextArray(chars2); while (i1 < chars1.length && i2 < chars2.length) { if (chars1[i1] == chars2[i2]) { i1++; i2++; } else if (next[i2] == -1) { // i2 == 0 i1++; } else { i2 = next[i2]; } } // 数组中下标是6,是第7个,加不加1取决于返回什么 return i2 == chars2.length ? i1 - i2 : -1; } /** * KMP的辅助数组 * @param chars * @return */ public static int[] getNextArray(char[] chars) { if (chars.length == 1) { return new int[] {-1}; } int[] next = new int[chars.length]; next[0] = -1; next[1] = 0; int i = 2; int cn = 0; while (i < next.length) { if (next[i - 1] == next[cn]) { next[i++] = ++cn; } else if (cn > 0) { cn = next[cn]; } else { next[i++] = 0; } } return next; } /** * 最长回文子串的长度 * @param string * @return */ public static int maxLcpsLength(String string) { if (string == null || string.length() == 0) { return 0; } char[] chars = string.toCharArray(); // charArr是辅助字符串,添加辅助字符 char[] charArr = new char[chars.length * 2 + 1]; int index = 0; for (int i = 0; i < charArr.length; i++) { // 数组从0开始,辅助字符放在偶数位置 charArr[i] = (i & 1) == 0 ? '#' : chars[index++]; } // 回文半径数组 int[] pArr = new int[charArr.length]; // 中心 int c = -1; // 右边界右边1个的位置,最右的有效区是R-1位置 int r = -1; // 最大值 int max = Integer.MIN_VALUE; // 求每个位置的回文半径 for (int i = 0; i < charArr.length; i++) { // i至少的回文区域,先给pArr[i], // pArr[2 * c - i]是i关于c的对称点的最大回文半径的值, // r-i是当i关于c的对称点的回文半径超过对应的r关于c的对称点时的值,r`-1肯定不等于r,但是无法判定r与2*i-r的值是否相等。 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]); } // 处理后的回文半径减1等于原始串的回文长度 return max - 1; } public static void main(String[] args) { // KMP String str = "abcabcababaccc"; String match = "ababa"; System.out.println(KMP(str, match)); // 最长回文子串 String str1 = "abc1234321ab"; System.out.println(maxLcpsLength(str1)); } }