next数组构造
KMP匹配过程
🔢next数组计算过程
next[j] = 模式串T[0..j-1]中最长相等前后缀的长度
当 T[j] != T[k] 时，k = next[k] 继续比较
当 T[j] != T[k] 时，k = next[k] 继续比较
模式串 T
next数组
🔍KMP匹配可视化
主串 S
模式串 T
0
比较次数
0
位移次数
-
主串指针 i
-
模式指针 j
💡算法说明
// KMP算法核心：利用next数组避免主串指针回溯
void getNext(String T, int next[]) {
int i = 0, j = -1; next[0] = -1;
while (i < T.length - 1) {
if (j == -1 || T[i] == T[j]) { i++; j++; next[i] = j; }
else j = next[j];
}
}
int KMP(String S, String T, int next[]) {
int i = 0, j = 0;
while (i < S.length && j < T.length) {
if (j == -1 || S[i] == T[j]) { i++; j++; }
else j = next[j];
}
if (j >= T.length) return i - j;
else return -1;
}