思路
image.png
image.png
image.png
Next数组
伪代码
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
next[j] = next[k];
} else {
next[j] = k;
}
} else {
k = next[k];
}
}
return next;
}
推导
- 当j=0时，
j=0
若，i应当右移一位，故
-
时, 说明j的前串与p的前串无相同部分
若，则P[0]与S[i]也不相同，直接右移，
若，
，判断P[0]与S[i]
-
应满足:
若,
若，则P[k+1]与S[i]也不相同，令
若，令
-
时,
P[k] != P[j]
令继续匹配
主算法
public static int KMP(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
int[] next = getNext(ps);
while (i < t.length && j < p.length) {
if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
i++;
j++;
} else {
// i不需要回溯了
// i = i - j + 1;
j = next[j]; // j回到指定位置
}
}
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
