​
​

活动地址：CSDN21天学习挑战赛

怕什么真理无穷，进一步有一份的欢喜。

【21天学习挑战赛】KMP模式匹配算法

✌我为什么参与挑战赛

1，机缘

读到研一了，暑假假期打开私信发现这个挑战赛就鼓起勇气参加了。

2，期待的收获

A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
C, 期待认识志同道合的领域同行或技术交流。
如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

🍉模式匹配算法？

对于子串的定位操作通常成为串的模式匹配,可以看下图就是匹配的过程

💬KMP模式匹配算法的定义

可以看到上面的匹配是一位一位的挪动，匹配算法很低效，KMP算法是前人发表的一种模式匹配算法来大大避免重复遍历的情况。

✨KMP模式匹配算法的优劣

优势

大大减低时间复杂度，从原来的O((n-m+1)*m)降低为O(n+m)

劣势

原理较复杂，实现困难

🍵KMP模式匹配算法的步骤

1. 构建next数组(请参考KMP学习资料)
2. 进行匹配

✍️ 算法实现

package wpc.leetbook.arrString;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class KMP {
    private int[] get_next(String T) {
        int m = T.length();
        int[] next = new int[m];
        next[0] = -1;
        int j = -1, i = 0;
        // j表示当前字符之前的串的前后缀的相似度
        while (i < m - 1) {
            // T[j] 表示前缀的单个字符
            // T[i] 表示后缀的单个字符
            if (j < 0 || T.charAt(j) == T.charAt(i)) {
                j++;
                i++;
                next[i] = j;
            } else {
                //如果字符不同就进行回溯，退到合适位置，i不变
                j = next[j];
            }
        }
        return next;
    }

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int m = haystack.length(), i = 0;
        int n = needle.length(), j = 0;
        //获取next数组
        int[] next = get_next(needle);
        while (i < m && j < n) {
            //两个字母相等，继续匹配
            if (j < 0 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                //j退到合适位置，i不变
                j = next[j];
            }
        }
        if (j == n) {
            return i - j;
        } else return -1;

    }

    @Test
    public void test() {
        int[] arr = get_next("abcabx");
        System.out.println(Arrays.toString(arr));
    }
}

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

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
⭐️ 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！