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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public int strStr(String haystack, String needle) {
int lenH = haystack.length(), lenN = needle.length();
if (lenN == 0) {
return 0;
}
String h = " " + haystack, n = " " + needle;

// Set jump table
int[] jump = new int[lenN + 1];
for (int i = 2, j = 0; i <= lenN; i++) {
char cI = n.charAt(i);
while (j > 0 && n.charAt(j + 1) != cI) {
j = jump[j];
}
if (cI == n.charAt(j + 1)) {
j++;
}
jump[i] = j;
}

// KMP body
for (int i = 1, j = 0; i <= lenH; i++) {
char cI = h.charAt(i);
while (j > 0 && n.charAt(j + 1) != cI) {
j = jump[j];
}
if (cI == n.charAt(j + 1)) {
j++;
}
if (j == lenN) {
return i - j;
}
}
return - 1;
}
}