Cfe58c598dfe8af307d6dd85cea41968
(难度Easy) Problem 28. Implement strStr()(字符串匹配-KMP算法)

链接

https://leetcode.com/problems/implement-strstr/

难度等级

Easy

题干

Implement strStr().

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

题意

输入两个字符串A,B,要求返回B串在A串当中第一次出现的位置,如果没有出现,则返回-1

样例

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

题解

这道题虽然是Easy难度,但是对于初学者而言一点也不Easy,而且涉及到了新的算法,所以很值得初学者们好好琢磨。

解法一: 暴力枚举

我们很容易想到暴力的方法,要判断一个字符串在另一个字符串当中是否出现过,我们只需要枚举A串当中所有的位置作为B串的开头,接着一位一位地匹配,看看是否满足要求,返回满足要求的第一个位置即可。

伪代码也不难写:

def match(A, B):
    for i in range(len(A)):
        flag = True
        for j in range(len(B)):
            if A[i+j] != B[j]:
                flag = False
                break
        if flag:
            return i

但是这种做法的缺点也很明显,那就是复杂度太高。假设A串是aaaaaaaaaaab,B串是aaaaaab,那么我们几乎要把所有位置都便利到。所以整体的复杂度是A串的长度乘以B串的长度,也就是$O(nm)$。

很显然,这样做固然可行,但是却是不可以接受的。

解法二: KMP算法

top Created with Sketch.