左神算法-提升02-KMP、Manacher算法
KMP算法解决的问题
字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中开始的位置。
如何做到时间复杂度O(N)完成？
KMP算法的全部细节和实现讲解
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);
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] == str2[i2]) {
i1++;
i2++;
} else if (i2 == 0) { // next[i2] = -1
i1++;
} else {
i2 = next[i2];
}
}
// i2越界匹配成功，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;
int cn = 0; // 表示当前与i - 1位置比较的位置，也表示i - 1位置的最大前缀长度
while (i < next.length) {
if (ms[i - 1] == ms[cn]) {
next[i++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
}
Manacher算法解决的问题
字符串str中，最长回文子串的长度如何求解？
如何做到时间复杂度O(N)完成？
Manacher算法的全部细节和实现讲解
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 C = -1; // 中心位置
int R = -1; // 回文右边界+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]]) {
break;
}
pArr[i]++;
}
if (i + pArr[i] > R) { // 更新回文右边界&中心位置
R = i + pArr[i];
C = i;
}
max = Math.max(max, pArr[i]);
}
// return max - 1;
int res = Arrays.stream(pArr).max().getAsInt();
return res - 1;
}
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;
}