KMP算法
KMP算法
我是也能够理解算法的意思是什么,但是其实现确实还是比较复杂的,没有办法把代码写的人人都看得懂的那种程度,那没办法 只能跟以前学图论一样,先背板子吧。
public int strStr(String haystack, String needle) {
// 构建next数组,用于指示needle中匹配失败时应该回溯的位置
int[] next = new int[needle.length()];
int j = -1; // -1 代表完全没有匹配任何模版,下一个判断的索引是 0
next[0] = j;
// i 从 1 开始,因为 0 处失败必然是回到 -1
for (int i = 1; i < needle.length(); i++) {
// 当前字符匹配失败时,通过next数组回溯j的位置
while (j >= 0 && needle.charAt(i) != needle.charAt(j + 1)) {
j = next[j];
}
// 如果当前字符匹配成功,则更新j
if (needle.charAt(i) == needle.charAt(j + 1)) {
j++;
}
// 将当前位置的j值记录到next数组中
next[i] = j;
}
j = -1;
// 注意 i 从 0 开始,j 的意思是已经匹配的索引,而不是下一个判断的索引
for (int i = 0; i < haystack.length(); i++) {
// 当前字符匹配失败时,通过next数组回溯j的位置,j一般就会变回-1
while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
j = next[j];
}
// 如果当前字符匹配成功,则更新j
if (haystack.charAt(i) == needle.charAt(j + 1)) {
j++;
}
if (j == needle.length() - 1) {
return i - j;
}
}
// 未找到匹配的子串,返回-1
return -1;
}
我的理解就是 j 代表的是已经匹配成功的索引,所以初始化是 -1,后面每次都是判断 j+1 的索引位置,成功才把 j 加上去。然后就是两个循环中 i 的初始值不一样,我们需要保证一个循环的终点也就是 next[0],就像递归要有边界条件,我们在 while 中也需要一个终止条件,那就是让 j 变成 -1 。所以 next[0] 必须是 -1 。
Comments