KMP

KMP算法的大致思路：进行模式匹配时，主串指针不回溯，只有模式串回溯，时间复杂度为 $O(n + m)$，其中 $n$ 为主串长度， $m$ 为模式串长度

构建next数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void getNext(String pp, int[] next) {
    int m = pp.length();
    // 使下标从 1 开始
    pp = " " + pp;
    char[] p = pp.toCharArray();
	for (int i = 1, j = 0; i < m; ) {
        if (j == 0 || p[i] == p[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j]; // 匹配失败
        }
    }    
}

KMP模式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int indexKMP(String ss, String pp, int[] next) {
    int n = ss.length(), m = pp.length();
    // 使下标从 1 开始
    ss = " " + ss;
    pp = " " + pp;
    char[] s = ss.toCharArray(), p = pp.toCharArray();
    
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || s[i] == p[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    // 匹配成功
    // if (j > m) return i - m - 1; // 返回从 0 开始的下标
    if (j > m) return i - m; // 返回从 1 开始的下标
    else return -1; // 匹配失败 
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int KMP(String ss, String pp) {
    int n = ss.length(), m = pp.length();
    // 使下标从 1 开始
    ss = " " + ss;
    pp = " " + pp;
    char[] s = ss.toCharArray(), p = pp.toCharArray();
    // 求 next 数组，next 数组与模式串（匹配串）相关
    int[] next = new int[m + 1];
    for (int i = 1, j = 0; i < m; ) {
        if (j == 0 || p[i] == p[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j]; // 匹配失败
        }
    }
    // KMP模式匹配
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || s[i] == p[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j > m) return i - m - 1; // 匹配成功
    else return -1;
}
  • 时间复杂度：$O(n + m)$
  • 空间复杂度：$O(m)$