search

Knuth–Morris–Pratt 字符串匹配

当初刚转CS研究生，上九章算法班的时候，第一讲就是 strStr() ，黄老师特别强调面试时候不要因为知道某个 fancy 算法就去写。当时觉得面试时候写个 KMP 挺高大上的，有炫技嫌疑而且容易犯错误。

上了两年计算机课之后，我现在觉得 KMP 这东西挺简单的，很好实现又很好理解，为什么不写。感谢马里奥，在考试题里能出现“ linear time 实现支持 wildcard 的 KMP ”算法之后，写个原版的 KMP 简直是太良心了。。。

两年的时间，真快啊。

这题的 KMP 解法已经在 LeetCode 论坛上到处都是而且被提交烂了。不过我自己还是更喜欢 CLRS 上的伪代码。

public class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack.length() < needle.length()) return -1;
        if(needle.length() == 0) return 0;

        int[] next = getNext(needle);
        int q = 0; // number of chars matched in pattern
        for(int i = 0; i < haystack.length(); i++){
            while(q > 0 && needle.charAt(q) != haystack.charAt(i)){
                q = next[q - 1];
            }
            if(needle.charAt(q) == haystack.charAt(i)){
                q ++;
            }
            if(q == needle.length()){
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    private int[] getNext(String pattern){
        int M = pattern.length();
        int[] next = new int[M];
        int k = 0; // number of chars matched in pattern
        for(int i = 1; i < M; i++){
            while(k > 0 && pattern.charAt(k) != pattern.charAt(i)){
                k = next[k - 1];
            }
            if(pattern.charAt(k) == pattern.charAt(i)){
                k ++;
            }
            next[i] = k;
        }

        return next;
    }
}

hashtag
next[] 里的 k = 正确 match 的长度

hashtag
next[] 中，每个位置的数字是由 k 赋值的，代表“如果下一个字符串挂了，在我这个位置截止的字符串正确 match 的长度是多少”

  • 于是这个 getNext() 函数就很好解释了。 next[] 的大小等于 pattern 长度，k 初始值为 0.

  • next[0] = 0 因为 substring 长度如果只为 1 的话，前面没东西和它匹配。

  • 于是开始一个 while 循环，迭代寻找如果当前字符串挂了，我们目前的最长 suffix 到底多长，有可能会跳很多步。这个写法有点类似于 disjoint set 里面 weighted union-find 的 path compression 实现，就是一个 while 循环迭代赋值 index 一直到正确的 / base case 为止。 k > 0 这个条件很重要，不然如果在第一个字符串挂了之后，会去找 next[-1] 就越界了。

  • 每次我们在 index k 上挂的时候，是去找 next[k - 1] 的 k 值是什么。原因是 length 与 index 间有 1 的 offset ，我们去看 index = k 的位置其实是在考虑要不要把 length 设成 k + 1.

  • 此后如果当前字符串匹配，就把 k + 1，赋值到当前 next[i] 上。赋值之后就不会再改了。

hashtag
match 函数的逻辑基本和 getNext 完全一样，k 代表目前的 text 上 match pattern 的字符串长度。

  • 当 q = pattern.length() 的时候，从 i 开始往回挪动 q 步，因为挪动前 i 处在 pattern 最后一个字符，要再往回挪动一个位置。

  • i - needle.length() + 1;

hashtag
(G) 面经题 http://www.1point3acres.com/bbs/thread-199776-1-1.htmlarrow-up-right

hashtag
给两个字符串，找到第二个在第一个中第一次出现的位置（自己写string.indexOf这个函数吧），followup1，找一个字符串中period的字符段，followup2，找到period次数最少的，例如abababab，ab出现了4次，abab出现了2次，返回2

Previous5/24 String 杂题NextLempel–Ziv–Welch 字符串压缩算法

Last updated