KMP算法

个人理解

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

如何计算前缀

参考卡哥网站 前缀计算

然后利用前缀表去做匹配

leetcode 28

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;
    }
}
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