思路

匹配串（i下标）：BBCABCABCABD
模式串（j下标）：   ABCABD
1
2

• 已知，C和D不匹配，C和D之前的字符串是匹配的。不能完全匹配，就选择部分匹配，以减小i和j下标回退的位数。
• 部分匹配字符串：部分匹配的字符串不用再次比较。当前匹配字符串(ABCAB)的 最长相等前后缀字符串(AB)。直接让i下标字符C和部分匹配字符串(AB)的下1个位置的字符C比较
• 求解部分匹配值：字符串的 最长前缀字符串=最长后缀字符串中 的字符数量
• 求解部分匹配值表：模式串(ABCABD)从1个字符做字符串，2个字符做字符串，…，(模式串长度-1)个字符做字符串。求某个字符串的部分匹配值

求解部分匹配值表：模式串(ABCABD)

• A的前缀空集，后缀空集，最长相等前后缀字符串字符数量=0
• AB的前缀{A}，后缀{B}，最长相等前后缀字符串字符数量=0
• ABC的前缀{A,AB}，后缀{C,BC}，最长相等前后缀字符串字符数量=0
• ABCA的前缀{A,AB,ABC}，后缀{A,CA,BCA}，最长相等前后缀字符串字符数量=1
• ABCAB的前缀{A,AB,ABC,ABCA}，后缀{B,AB,CAB,BCAB}，最长相等前后缀字符串字符数量=2
• ABCABD的前缀{A,AB,ABC,ABCA,ABCAB}，后缀{D,BD,ABD,CABD,BCABD}，最长相等前后缀字符串字符数量=0

求解部分匹配值表：模式串(ABCABD)

• A字符串的部分匹配值=0，AB字符串的部分匹配值=0，…，ABCA的部分匹配值=1，ABCAB的部分匹配值=2
• 到B(i=4)之后的字符不能完全匹配了，但是前next[4]=2个字符仍然是部分匹配的

代码

package xcrj.string;

/**
 * 模式匹配算法
 */
public class KMP {
    /**
     * 部分匹配表
     * 本质就是求已匹配的子串的最长部分匹配前缀的字符数
     * 

     * 当无法全部匹配时，进行部分匹配j起始位置
     * 模式串的子串的最长前缀=最长后缀 的字符数，就是当前模式串子串的部分匹配
     * 部分匹配值就是模式串的子串的子串的字符数
     *
     * @param pattern 模式串
     * @return int[]next 部分匹配表
     */
    private static int[] partialMatchingTable(String pattern) {
        int[] next = new int[pattern.length()];
        // i=0,1个字符做1个子串时，部分匹配值=0
        next[0] = 0;
        // 求得0~i-1子串的部分匹配值基础上，再求0~i子串的部分匹配值
        for (int i = 1, j = 0; i < pattern.length(); i++) {
            // i，j字符不匹配时，j退回到0~j-1子串的部分匹配值
            while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                // j退回到0~j-1子串的部分匹配值（0~j-1的子串都是部分匹配的）
                j = next[j - 1];
            }
            // i,j字符匹配，比较下一个字符
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            // 0~i的子串的部分匹配值=j
            next[i] = j;
        }

        return next;
    }

    /**
     * kmp算法
     *
     * @param match   匹配串
     * @param pattern 模式串
     * @return -1表示匹配串中不存在模式串，非-1表示模式串在匹配串的起始位置
     */
    public static int kmp(String match, String pattern) {
        // 获取部分匹配表
        int[] next = partialMatchingTable(pattern);
        // i匹配串下标,j模式串下标
        for (int i = 0, j = 0; i < match.length(); i++) {
            // 不完全匹配时，进行部分匹配：i，j字符不匹配时，从模式串最长部分匹配前缀之后开始比较
            while (j > 0 && match.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            // i，j字符匹配，比较下一个字符
            if (match.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            // 模式串匹配完成，返回模式串在匹配串的起始位置
            if (j == pattern.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String match = "CBCBA";
        String pattern = "CBA";
        int idx = kmp(match, pattern);
        System.out.println("模式串在匹配串的起始位置：" + idx);
    }
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74