LeetCode-28.Implement strStr-KMP算法

Description:
 Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. 

这是我刷的为数不多的LeetCode Easy题之一(其实也没刷多少),题的意思非常简单,给出H和N两个字符串,求N在H字符串中出现的位置。

此题意在考察最为基础的BF算法,也就是暴力求解的方法:

先从H和N的第一个字符(H[0]和S[0])依次往后匹配,如匹配失败,则将H开始匹配的位置向后移1个单位,重新匹配(H[1]和S[0]),直到匹配成功位置。若到最后也没有匹配成功,返回-1。

最坏的情况下,时间复杂度为O(H*N),即每次都是匹配到N串结尾时匹配失败,然后H串回溯到开头+1的位置,重新开始匹配。这种情况是非常糟糕的。

另一种常用的匹配算法为KMP算法,它记录了子串的匹配信息,当匹配失败时,不将主串回退,而是将模式串调整到合适的位置。

KMP算法分为两部分,求Next数组与计算部分,Next数组记录了当匹配失败时,N串的索引应该调整到什么位置(以对齐与主串头部相同的部分)。时间复杂度为O(H*N)

KMP算法的详细解释在此不详细阐述,Google即可得到大量文章。

然而,我们需要考虑一下,是否KMP算法一定就优于BF算法呢?当然不,甚至可以说大多数情况下,BF算法优于KMP算法。

例如:

H = ABCDEFGHIJKLNMOPQR
N = HIJK

这种情况下,模式串N并没有相同部分,每次匹配都与BF算法一样,必须回到H串开头+1的位置重新匹配,并且,还多了计算Next数组的时间开销。

想象一下,我们一般在哪里进行IndexOf操作?通常在一长篇文章里,一个含有大量内容的网站中。那么在这些信息中,在模式串和主串中出现大量相同部分的概率几乎没有

最后附上KMP模板

class Solution {
    char[] str;
    char[] pattern;
    int[] next;

    public int strStr(String haystack, String needle) {
        str = haystack.toCharArray();
        pattern = needle.toCharArray();
        initNext();
        return KMP();
    }

    private void initNext() {
        next = new int[pattern.length + 1];
        next[0] = -1;
        int i = 0;
        int j = -1;
        while (i < pattern.length) {
            if (j == -1 || pattern[i] == pattern[j]) {
                next[++i] = ++j;
            } else {
                j = next[j];
            }
        }
    }

    private int KMP() {
        int i = 0;
        int j = 0;
        while (i < str.length && j < pattern.length) {
            if (j == -1 || str[i] == pattern[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == pattern.length) {
            return i - j;
        } else {
            return -1;
        }
    }
}

Azure99

大二蒟蒻,喜欢折腾vps、玩机,偶尔写写代码

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注