KMP算法

卡尔老师视频链接

KMP算法：

• KMP算法，全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的高效算法。它的主要思想是利用已经匹配过的字符信息，避免不必要的回溯，从而提高匹配的效率。
• KMP算法的核心是构建一个辅助数组next，用来记录模式串中每个字符对应的最长公共前缀和后缀的长度。通过这个数组，可以在匹配过程中根据已匹配的前缀信息，跳过一些不必要的比较。

具体的匹配过程如下：

1. 首先，根据模式串构建next数组。next[i]表示模式串中以第i个字符结尾的子串的最长公共前缀和后缀的长度。
2. 然后，从文本串的第一个字符开始，与模式串的第一个字符进行比较。
3. 如果当前字符匹配成功，则依次比较下一个字符，直到模式串结束或者字符不匹配。
4. 如果当前字符匹配失败，则根据next数组的值，移动模式串的位置，继续与文本串中的下一个字符进行比较。
   • 如果next[j] = -1，表示模式串需要移动到下一个位置，即i++；
   • 如果next[j] ≠ -1，表示模式串需要向右移动的位置为j - next[j]。

KMP算法的时间复杂度为O(m +
n)，其中m为模式串的长度，n为文本串的长度。相比于朴素的字符串匹配算法，KMP算法通过利用已匹配的前缀信息，避免了一些不必要的比较，从而提高了匹配的效率。

public class Kmp {
    // 构建next数组
    private int[] buildNext(String pattern) {
        int[] next = new int[pattern.length()]; // next数组，用于记录最长公共前缀和后缀的长度
        int i = 0; // pattern的索引
        int j = -1; // next数组的值

        next[0] = -1; // 第一个字符的next值为-1

        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }

        return next;
    }

    // KMP算法匹配
    public int kmpMatch(String text, String pattern) {
        int[] next = buildNext(pattern);
        System.out.println("next数组：");
        for(int i=0;i<next.length;i++){
            if(i==next.length-1){
                System.out.print(next[i]+"\n");
            }else{
                System.out.print(next[i]);
            }
        }
        int i = 0; // text的索引
        int j = 0; // pattern的索引

        while (i < text.length() && j < pattern.length()) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j == pattern.length()) {
            return i - j; // 返回匹配的起始位置
        } else {
            return -1; // 没有匹配的子串
        }
    }

    // 测试
    public static void main(String[] args) {
        String text = "abbabbababaaababaaababab";//文本串
        String pattern = "ababaaababaa";//模式串
        Kmp kmp=new Kmp();
        int index = kmp.kmpMatch(text, pattern);

        if (index != -1) {
            System.out.println("在位置 " + index + " 处找到匹配的子串");
        } else {
            System.out.println("未找到匹配的子串");
        }
    }
}
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

解释一下，KMP算法中的next数组的构建部分：

1. 首先，创建一个长度为模式串长度的next数组。然后，定义两个指针i和j，分别用于指向模式串中的字符和next数组中的值。
2. 接下来，将第一个元素的next值设置为-1，表示没有公共前缀和后缀。
3. 然后，使用while循环遍历模式串中的字符，直到遍历到倒数第二个字符。在循环中，判断j的值是否为-1或者当前字符与对应位置的字符相等。
4. 如果j的值为-1，表示没有找到公共前缀和后缀，此时将i和j都向后移动一位，并将next[i]的值设置为j。
5. 如果当前字符与对应位置的字符相等，表示找到了公共前缀和后缀，此时将i和j都向后移动一位，并将next[i]的值设置为j。
6. 如果j的值不为-1且当前字符与对应位置的字符不相等，表示当前字符与j位置处的字符不匹配，需要将j的值更新为next[j]，即回退到之前相同前缀的位置。
7. 最后，返回构建好的next数组。

简单地说一下next数组吧：
1、先求模式串每个子串的最长公共前后缀
2、然后看题目要求（有时候你得两种情况都抽一眼）
（1）下标从0开始：将上面求的数组整体右移一位（第一位补-1）
（2）下标从1开始：将第一种情况求得的数组加1