28. 实现 strStr()
KMP算法解决串的模式匹配
28.题目链接-来源:力扣(LeetCode)
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。
说明:
当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1:
输入:haystack = “hello”, needle = “ll”
输出:2
思路:
此题是 KMP 算法的典型应用。记 haystack 的长度为 h,needle 的长度为 n,则暴力解法可以在 O(hn)的复杂度内完成查找(每次在 haystack 中移动到新的一位时,最坏情况下要从此处开始依次与 needle 作比较)。
考虑优化解法。我们的问题是,是否每次匹配失败后,needle 的指针都要回退到开头?能否经过一些处理,减少指针跳转的次数?答案就是 KMP 算法。
对于形如 “abcabd” 的 needle 串,我们考虑暴力法和 KMP 法的指针跳转情况。对于暴力法,一旦我们匹配失败,指针就要跳转到开头处进行比较;而对于 KMP法,当我们的指针指向 ‘d’ 所在的位置时,匹配失败了,则我们(希望)跳转到 ‘c’ 所在的位置进行比较,这样我们可以省下一半的时间。我们现在来确定这个跳转规则。
我们可以这样考虑,记 “abcabd” 的指针为 i,对应的指针序号为 012345,我们维护一个与 needle 长度一样跳转表 jump,记录每一位访问失败时指针应当跳转向何处。对于数组中我们的跳转目的,其指针记为 j。i、j均从 0 开始。
- 为了兼容空串,我们将 needle 前方拼接上一个不会出现的字符,这里我选择空格 ‘ ‘,方便我们后续处理。
- 对于首字符 i = 1,匹配失败后应当回到开头,故我们可以定义 jump[1] = 0。
- 对于 i >= 2,由于 needle[i] != needle[j],即我们并不能找到合适的重用信息,我们希望 j 往 jump[j] 跳转,看能否找到合适的 needle[j] = needle[i] 可以让我们复用,直到 j = 0 若还未找到,我们认为不存在,于是默认跳转为 0,否则,应当设定 jump[i] = j。
- 对于 i = 4,我们发现 needle[i] = needle[j],即出现了可以复用的情况,即可维护当前 jump[i] = j + 1,同时让 j 指向下个位置。
经过这样预处理之后的 jump 数组,即可用来帮助我们遍历主字符串 haystack。遍历规则类似我们生成 jump 时的规则,当指向 needle 的指针越界,则表示我们已经找到了合适的串,返回该串的起点坐标即可。
时间复杂度:O(h + n)
空间复杂度:O(n)
实现:
1 | class Solution { |