【必背模板】字符串匹配问题的通用解法：KMP 算法 ...
【必背模板】字符串匹配问题的通用解法：KMP 算法 ...
题目描述
这是 LeetCode 上的「28. 实现 strStr()」，难度为 Easy。
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。
如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当
是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当
是空字符串时我们应当返回 0 。
这与C语言的
以及 Java的
定义相符。
朴素解法
直观的解法的是：枚举原串 ss 中的每个字符作为起点，构造一个和匹配串 pp 一样长度的子串 sub ，将 sub 和 pp 做对比。
代码：
class Solution {
public int strStr(String ss, String pp) {
int n = ss.length(), m = pp.length();
for (int i = 0; i < n - m + 1; i++) {
String sub = ss.substring(i, i + m);
if (sub.equals(pp)) return i;
}
return -1;
}
}
- 时间复杂度：
n为原串的长度，m为匹配串的长度。其中枚举的复杂度为
，构造和比较字符串的复杂度为
。整体复杂度为
- 空间复杂度：
KMP 解法
KMP 算法是一个快速查找匹配串的算法，时间复杂度为
。
建议和三叶在「5. 最长回文子串」中提供的 Manacher 算法一样，进行背过。
KMP 算法的应用范围要比 Manacher 算法广，Manacher 算法只能应用于「回文串」问题，较为局限，而「子串匹配」问题还是十分常见的。
背过这样的算法的意义在于：相当于大脑里有了一个时间复杂度为
的 api 可以使用，这个 api 传入一个原串和匹配串，返回匹配串在原串的位置。
从实用角度出发，背过模板甚至比真正理解 KMP 更重要，很长时间不用 KMP 了，你问我 KMP 是如何优化匹配的，我大概要想好一会，但是 KMP 算法还是能随时默写出来。
一些相关的注释我已经写到代码里：
class Solution {
// KMP 算法
// ss: 原串 pp: 匹配串
public int strStr(String ss, String pp) {
if (pp.isEmpty()) return 0;
// 分别读取原串和匹配串的长度
int n = ss.length(), m = pp.length();
// 原串和匹配串前面都加空格，使其下标从 1 开始
ss = " " + ss;
pp = " " + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
// 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
int[] next = new int[m + 1];
// 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
for (int i = 2, j = 0; i <= m; i++) {
// 匹配不成功的话，j = next(j)
while (j > 0 && p[i] != p[j + 1]) j = next[j];
// 匹配成功的话，j++
if (p[i] == p[j + 1]) j++;
next[i] = j;
}
// 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
for (int i = 1, j = 0; i <= n; i++) {
// 匹配不成功 j = next(j)
while (j > 0 && s[i] != p[j + 1]) j = next[j];
// 匹配成功 j++
if (s[i] == p[j + 1]) j++;
// 如果匹配成功了，直接返回
if (j == m) return i - m;
}
return -1;
}
}
- 时间复杂度：
- 空间复杂度：构建了
数组。复杂度为
最后
这是我们「刷穿 LeetCode」系列文章的第 No.28 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。