个人理解

我理解的KMP 算法就是记录前缀与后缀，每当遇到不匹配的时候由于后缀已经被匹配过，所以下次应该跳到匹配过的后缀也就是相应的前缀后面在进行匹配。

如何计算前缀

参考卡哥网站 前缀计算https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E6%80%9D%E8%B7%AF

然后利用前缀表去做匹配

在这里插入图片描述

leetcode 28

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
class Solution {
    
    public int strStr(String haystack, String needle) {
    
        int[] next=new int[needle.length()];
        int j=0;
        next[0]=j;
        for(int i=1;i<needle.length();i++){
    
        	//因为找相等的前缀所以遇到不等的就也跳前缀
            while(j>0&&needle.charAt(i)!=needle.charAt(j)){
    
                j=next[j-1];
            }

            if(needle.charAt(i)==needle.charAt(j)){
    
                j++;
            }
            next[i]=j;
        }

        int i=0;
        j=0;
        while(i<haystack.length()){
    
        	//遇到不等的就跳前缀
            while(j>0 && haystack.charAt(i)!=needle.charAt(j)){
    
                j=next[j-1];
            }
            if(haystack.charAt(i)==needle.charAt(j)){
    
                j++;
            }
            if(j==needle.length()){
    
                return i-j+1;
            }
            i++;
        }
        return -1;
    }
}