CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第九天|KMP算法

Posted on Edited on

今天的核心内容在于理解KMP算法，还在努力理解中ing～

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
45
46
47
48
49
50
51
class Solution {
    public int strStr(String haystack, String needle) {

        int hayIndex = 0, needleIndex = 0;
        int ans = -1;
        char c1, c2;

        // at least we need to full scan the haystack string once
        while (hayIndex < haystack.length()) {
            // iff the first char is the same should we compare the left elements
            while (hayIndex < haystack.length() && (c1 = haystack.charAt(hayIndex)) != needle.charAt(0) ) {
                hayIndex++;
            }
            
            // if there is no same first char
            if(hayIndex == haystack.length()) {
                return -1;
            }else{
                // else let's compare the two str
               
                // first, let's record the hayIndex
                ans = hayIndex;

                while (needleIndex < needle.length() && hayIndex < haystack.length()) {
                    c1 = haystack.charAt(hayIndex);
                    c2 = needle.charAt(needleIndex);
                    if(c1 == c2) {
                        needleIndex++;
                        hayIndex++;
                    }else{
                        break;
                    }
                }

                // if needleIndex is less than needle.length(), it is not the same word
                if(needleIndex < needle.length()){
                    // let's reset hayIndex back to next char in hayStack
                    // and needleIndex to its first char
                    hayIndex = ans + 1;
                    ans = -1;
                    needleIndex = 0;
                }else{
                    return ans;
                }

            }
        }

        return ans;
    }
}

这是没有学习KMP算法前写的朴素解法。

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
class Solution {
    public int strStr(String haystack, String needle) {
        int i = 0, j = 0;
        int nh = haystack.length();
        int nn = needle.length();
        int[] next = getNext(needle);
        
        while ( i < nh) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                
                if ( j == nn){
                    return i - j;
                }
            }else{
                if (j > 0) {
                    j = next[j - 1];
                }else{
                    i++;
                }
            }
        }

        return -1;
    }

    public int[] getNext (String str){
        char[] pat = str.toCharArray();
        // i - > the first element in suffix
        int i = 1;
        // j-> the first element in the prefix substring
        int j = 0;

        int[] next = new int[pat.length];

        while ( i < pat.length) {

            if( pat[i] == pat[j] ) {
                next[i++] = ++j;
             }else {
                if( j == 0) {
                    next[i] = 0;
                    i++;
                }else {
                    j = next[j - 1];
                }
            }


        }

        return next;
    }
}

经过一番学习后，理解了KMP算法的大体思想，不过这里有一些细节之处可能再写时还要进一步的思考。

在KMP算法的学习中发现这个po主的视频讲解的最好，以上代码参考了https://www.bilibili.com/video/BV1iJ411a7Kb?p=5&vd_source=5d8279a9d134034c9a085489dde3d4ac的思路。