SLA-2

April 10 2022

Source Code

今天看了KMP，没有精力看别的source code了

Leetcode

https://leetcode.com/problems/reverse-words-in-a-string/ 151. Reverse Words in a String

Practice of using several typical String util methods:

  • trim()
  • spli()
  • Join()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String reverseWords(String s) {
        String[] arr = s.trim().split(" +");
        
        int i = 0;
        int j = arr.length - 1;
        while (i < j) {
            swap(i, j, arr);
            i++;
            j--;
        }
        
        return String.join(" ", arr);
    }
    
    public void swap(int i, int j, String[] arr) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

https://leetcode.com/problems/implement-strstr/ 28. Implement strStr()

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
class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = new int[needle.length()];
        buildNext(next, needle);
        
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) j++;
            if (j == needle.length()) return i - needle.length() + 1;
        }
        return -1;
    }
    
    private void buildNext(int[] next, String s) {
        char[] pat = s.toCharArray();
        next[0] = 0;
        int j = 0;
        for (int i = 1; i < pat.length; i++) {
            while (j > 0 && pat[i] != pat[j]) j = next[j-1];
            if (pat[i] == pat[j]) j++;
            next[i] = j;
        }
    }
}

个人认为核心思想有两个：

  • j，代表的是当前最长匹配前缀的长度，同时显而易见的是，这个长度也是当前前缀的下一个要匹配的目标位置。

  • 另一个重点是【回退】或者我们可以说成是【退而求其次】， 也就是j = next[j-1]这个操作。为什么要这样回退？

**首先我们定义什么是【KMP式回退】，就是当我们出现失配时，将j指针先回退到j之前可能出现的最长匹配前缀的下一个位置。**

接下来我们先解决一个疑问：当我们回退的时候，为什么不能直接让j–呢？
是因为我们比较j和i的时候，实际上基于了一个隐含条件：
Pat[j-1] == pat[i-1]
Pat[j-2] == pat[i-2]….
由此我们才能比较j和i，这样才有意义。
而简单粗暴的用i去试图匹配j-1这个位置显然不再能满足以上的这一系列隐含条件了。

那么为什么要回退到next[j-1]呢？
因为我们现在已经知道[j] != [i]了，因为KMP的本质就是为了让我们不要每次失配就回到原点，对么？

因此我们就利用已经构建好的【0到i-1】的next来帮助我们回退。

这就是很多文章中都提到的递归的思想。
即：在构建next的过程中，当出现失配时，我们就利用已经构建好的部分来进行一个【KMP回退】而不是暴力解法中的回退。

如果再具体来说，当构建过程中我们发现失配时，暴力解法是什么样的呢？
暴力解法时，当j 和 i出现失配，我们直接比较0和i是否相等。也就是比较最靠前的一个前缀（仅包含第一个字符），和最靠后的一个后缀（仅包含i这个位置的字符）是否匹配。

注意以上这个写法中，next[i]表示的是包含i这个位置的字符，也就是[0, i] 这个范围内的最长匹配前缀后缀长度。因此回退时，是将j回退为next[j-1]

用一个例子更直观的说明在buildnext过程中这样做的优势


1
2
3
4
5
6
7
8
9
10
11
12
13
14
0 1 2 3 4 5 6 7 8 9 10 11 12 13
x x x x a x c d e x x  x  x  x
0 1 2 3 0 1 0 0 0 1 2  3  4  ?

我们求next[13]
此时j = 4, i = 13
我们比较[j] 和 [i]
此时实际上存在一个隐含的前提：
[0, 3] == [9, 12]
就是说我们之所以可以去比较[j]和[i]是因为他们前面的j-1长度的字符串一定是相等的。

此时失配，因此我们进行回退。回退的位置是next[j-1], 也就是next[3] = 3
j = 3， 我们匹配[3] 和 [i]， 匹配成功，
next[i] = 3 + 1 = 4.



根据如上的例子，为什么KMP优于暴力解法呢？因为:
[0, 3] == [9, 12]

这是最重要的一个隐含条件。

假设说当next[3] = k，也就是[0, 3]里面有长度为k的前后缀匹配，由于以上隐含条件，我们可以得到[9, 12]中一定也存在这样长度的前后缀匹配。

并且[0, 3]中匹配的前缀，一定也等于[9, 12]中匹配的后缀。
（在以上的例子中，[0, 3]匹配的前缀是xxx, [9, 12]中匹配的后缀也是xxx



写出来的话，就是[0, k-1] == [12-(k-1), 12]

仔细观察这个等式，这是什么呢？

这就是我们接下来有必要去比较[k] 和 [i]的隐含条件。



也就是说正因为有这个隐含条件的成立，我们比较[k] 和[i]才有意义。当k 和 i匹配成功时我们才达到了shortcut的效果。（如果没有这个隐含条件的话，[k] == [i] 没有任何意义，只能说明一个字符相等，不能说明前缀和后缀成功匹配了。）



这也正是KMP相比于暴力解法的优势所在。



此处我们再次试图一句话解答上文提到的问题： **j = next[j-1] 即 j = k这个操作。为什么要这样回退？ 是因为这样回退之后存在[0, k-1] == [12-(k-1), 12] 这个先决条件，致使我们有机会在[k] == [i]的情况下避免出现暴力解法中那样回退到0的过度回退。**

Architecture

以前准备面试的过程中，KMP我背了两次。。。

第一次找实习的时候就背KMP，后来找全职又背KMP的next怎么生成。

知道昨天我仍然没明白为什么KMP要这样设计，也说不清楚为什么要这样求next数据，更说不清楚为什么要这样回退。

希望这一波学习中，可以稳扎稳打把每个知识点都吃透，形成自己的理解。