字符串算法-KML算法详解

KML 算法用来处理字符串匹配的问题。核心思想是当出现字符串不匹配时，根据之前已经匹配的文本内容，避免从头再去做匹配。

举例：

字符串，原始字符串，模式串是否属于字符串的一部分；
模式串，字符串的子串，用来匹配的。
对应字符串与模式串如下：
字符串：aabaabaafa
模式串：aabaaf
暴力破解方式为2层循环，一个字符一个字符交替进行匹配，此时时间复杂度为 n * m。
使用KML算法匹配，从第一个开始匹配，匹配到b != f的时候，不是从头开始匹配，而是从模式串的b开始往后匹配，可以一直匹配的末尾，字符串匹配到最后一个的下标减模式串的长度（8-6=2），即是结果

概念

能更清晰说明白KML算法，需要厘清几个概念

  • 前缀：包含首字母，不包含尾字母的所有子串
  • 后缀：包含尾字母，不包含首字母的所有子串
  • 最长相当前后缀：字符串的前缀后缀相当的子串中，最长的子串
  • next数组：存放遇到冲突后，回退下标，计算方式为最长相当前后缀长度

next数组

  • 赋值内容：直接存最长相当前后缀长度，开头存负一整体右移，最长相当前后缀减一
  • 计算逻辑：
    • 从第一个子串开始逐个循环
    • 前一位子串的最长相当前后缀的基础上分析，当前子串的最后一位=前一个最长相当前后缀长度所在下标的字符，则当前子串的最长相当前后缀加一，因为前面的在上一步已经判断过了
    • 当前子串的最后一位 != 前一个最长相当前后缀长度所在下标的字符，因为上一个最长相当前后缀可知前面的比较结果已经知道了，所以不用全部回退，只需要找到前一个下标的next数组中的最长前档前后缀的长度，回退到那个位置继续比较，直到相当或到头，记录最长相当前后缀在next当前的下标
  • 方便理解的几个模式串例子：aabaaf-010120、afbafaf-0001212、afbafafbafcaf-0001212345012

实现示例

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
/**
 * 练习KML算法
 *
 * @param haystack
 * @param needle
 * @return
 */
public int strStr(String haystack, String needle) {
    if (needle.length() == 0 || needle.length() > haystack.length()) {
        return -1;
    }

    char[] cHaystack = haystack.toCharArray();
    char[] cNeedle = needle.toCharArray();

    // 计算next数组
    // next 数组是模式串的最长相当前后缀的长度组成的数组
    // 前缀表：包含首字母，不包含尾字母的所有子串
    // 后缀表：包含尾字母，不包含首字母的所有子串
    // 最长相当前后缀：字符串的前缀表中与后缀表相当的子串中，最长的那个子串
    int[] next = getNext(cNeedle);

    int i = 0;
    int j = 0;

    while (i < cHaystack.length) {
        while (i < cHaystack.length && cHaystack[i] == cNeedle[j]) {
            if (j == cNeedle.length - 1) {
                return i - j;
            }
            j++;
            i++;
        }
        if (j == 0) {
            i++;
        } else {
            int preNextLen = next[j - 1];
            j = preNextLen;
        }
    }

    return -1;
}

private int[] getNext(char[] neddle) {
    int[] next = new int[neddle.length];

    int j = 0;
    next[0] = j;

    for (int i = 1; i < neddle.length; i++) {
        while (j > 0 && neddle[j] != neddle[i]) {
            // 原则是，比较过的不比较
            // 最长公共前后缀值得是该串的前后缀相当，当前冲突，对于前面的串不需要回退到第一个，
            // 只需要回退到公共前缀的末尾，如果不冲突，就出来结果了，如果还是冲突，则继续回退
            j = next[j - 1];
        }
        if (j >= 0 && j != i && neddle[j] == neddle[i]) {
            j++;
        }
        next[i] = j;
    }

    return next;
}