LeetCode30刷-字符串匹配-KMP_leetcode 30 最佳算法

本篇为LeetCode30刷，记录个人的学习记录，后续会补充

字符串匹配

No.1 暴力算法（BF）
采用逐个匹配的方法进行字符串的匹配，时间复杂度较为复杂，不推荐。
No.2 哈希值比较（RK）
原理：每一个字符都有一个哈希值，可以通过比较一个字符串的总哈希值来判断两个字符串有没有可能相等，如果相等就进行BF。
缺点：存在Hash冲突，可能退化为BF，所以并没有实质的提高效率。
No.3 ---------BM算法
原理：不同于以上的算法，BM算法是从后往前进行比较；
先介绍坏字符：如下图在倒数第三个字符出现问题，记下当前的索引（子串），向子串的前方找到问题字符（本题用A表示），直到子串的第一个索引位置找到A，子串向前移动至匹配。

好后缀：从后往前比较，如果后面几个字符（大于1个）匹配成功了，就把他们当作一个好后缀，下图中的BC就是好后缀

然后从子串向前查找，找到同样的BC，向前移动

下面才是字符串匹配重头戏！！

No.4 KMP算法
KMP算法是从前往后匹配，的具体参数如下

PMT就是找到目前的字符和之前的字符有没有一样的字符串
next数组的目的

下面演示next数组的值和PMT的关系
复制一个模式串，来找到共同的前缀和后缀，j和next[0]值初始为-1，
如果匹配不上，i++,j++，next[index]的值为上一个PMT值

如果匹配上，PMT++，i++，j++，next[index]为上一个PMT的 值

上述步骤代码如下

package Leetcode;

import java.util.ArrayList;

public class KMP_字符串匹配 {
    public static void main(String[] args) {
        String s1 = "daiojdad";
        String s2 = "io";
        char[] parent = s2.toCharArray();
        char[] str = s1.toCharArray();
        int len = parent.length;
        int[] next = new int[len];
        getNext(parent,next);
        int index = search(str,parent,next);
        System.out.println(index);

    }
    static void getNext(char[] parent,int[] next){
        next[0] = -1;
        int i = 0,j = -1;
        while(i < parent.length){
            if(j == -1){
                i++;
                j++;
            }
            else if(parent[i] == parent[j]){
                i++;
                j++;
                next[i] = j;
            }
            else{
                j = next[j];
            }
        }
    }
    //这个是kmp搜索功能
    static int search(char[] str,char[] parent,int[] next){ //str是主串，parent是模式串
        int i = 0;
        int j = 0;
        while(i < str.length && j < parent.length){
            if(j == -1 || parent[j] == str[i]){
                i++;
                j++;
            }
            else {
                j = next[j];
            }
        }
        if(j == parent.length){
            return i - j;
        }
        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
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

参考视频：链接1
参考视频：链接2