leetcode28.找出字符串中第一个匹配项的下标，KMP算法保姆级教程（带动图）
🎯 本文详细解析了“查找字符串首个匹配项下标”问题的多种解法，包括调用API、暴力求解和KMP算法。调用API如
indexOf方法可一行代码实现，简单高效但可能缺乏面试深度。暴力求解通过逐字符对比完成匹配，时间复杂度为O(m*n)，适合理解基础逻辑。KMP算法利用最长相同前后缀信息优化匹配过程，显著提高效率，适用于大规模字符串处理场景，时间复杂度为O(m+n)。文章结合案例深入讲解了KMP算法中前缀表的构建与应用，帮助读者全面掌握字符串匹配的核心技巧。
找出字符串中第一个匹配项的下标
题目
题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
调用API
这道题调用 API ，一行代码就可以搞定，效率还贼高。只是这样写，可能会被面试官屌一顿
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
暴力求解
为了方便理解，haystack在本文中使用text表示，needle在本文中用pattern表示。
【思路】
- 遍历文本串：从文本串的第一个字符开始，逐个字符作为匹配的起点。
- 尝试匹配模式串：
- 对于文本串的每一个起点，依次比较文本串和模式串的每一个字符。
- 如果所有字符都匹配，说明找到了模式串，返回匹配的起始位置。
- 如果某个字符不匹配，则停止当前起点的匹配，移动到文本串的下一个起点，重新开始匹配。
- 结束条件：
- 如果遍历完文本串的所有可能的起点，仍未找到匹配的子串，则返回 -1 。
假设text=“abcabeabcabfy”，pattern=“abcabf”，使用暴力方法求解过程如下：
/**
* 暴力破解
*
* @param text
* @param pattern
* @return
*/
public int strStr(String text, String pattern) {
for (int i = 0; i < text.length(); i++) {
boolean found = true;
for (int j = 0; j < pattern.length(); j++) {
if (i + j > text.length() - 1 || text.charAt(i + j) != pattern.charAt(j)) {
found = false;
break;
}
}
if (found) {
return i;
}
}
return -1;
}
时间复杂度是O(m*n)，m 是 text 的长度，n 是 pattern 的长度。虽然复杂度高，但是你别说，暴力求解还真可以 AC 。
KMP 算法
KMP 算法原理
KMP 算法的思想是：当出现字符不匹配时，利用部分已经匹配过的内容信息来避免pattern从头开始匹配。
还是用上面的数据：text=“abcabeabcabfy”，pattern=“abcabf”，KMP算法计算过程如下：
KMP 和暴力破解的区别是：
- 暴力求解：
pattern的指针直接回到 0 ，text的指针直接指向下一个起点 - KMP：指针直接跳过
pattern已经匹配过的部分，从下一个索引开始匹配
KMP为什么可以这样做呢？
如下图所示，两个指针分别指向 e 和 f 时，两者不匹配了，但是abcabe和abcabf的前面部分是匹配的，即abcab。通过找abcab的相同前后缀，可以发现text1和text2相同。又因为在前面的匹配中，已经知道text3和text2肯定是匹配的了，因此text3和text1也一定匹配。
为了提高算法效率，就可以省略text3和text1的匹配计算了，直接从下一个字符开始匹配，即 c 和 e 。
好，到这里，我们就已经知道 KMP 效率高的原因了，就是利用好相同前后缀的信息来跳过不必要的遍历。那我们如何记录相同前后缀信息呢，总不能每次遇到不匹配的字符，就去计算相同前后缀是吧，那这样效率就不高了。
记录相同前后缀信息
首先定义一下前缀和后缀
- 前缀：包括
pattern的第一个字母，不包括pattern的最后一个字母的所有子串，如aabaaf有如下前缀a、aa、aab、aaba、aabaa
- 后缀：包括
pattern的最后一个字母，不包括pattern的第一个字母的所有子串，如aabaaf有如下后缀f、af、aaf、baaf、abaaf
为了在计算的时候，能快速知道相同前后缀的长度是多少，我们**使用****前缀表**来记录该最长相同前后缀信息。假设pattern=aabaaf，前缀表如下：
pattern截取范围 | 子串（pattern[0,i]） | 最长相同前后缀 | 原因 |
|---|---|---|---|
| [0,1)、[0,0] | a | 0 | 只有一个字符，没有前缀，也没有后缀，所以长度是0 |
| [0,2)、[0,1] | aa | 1 | a 与 a，为什么是1，不是2 ？由上面的定义可知：aa的前缀只有 a |
| [0,3)、[0,2] | aab | 0 | |
| [0,4)、[0,3] | aaba | 1 | a 与 a |
| [0,5)、[0,4] | aabaa | 2 | aa 与 aa |
| [0,6)、[0,5] | aabaaf | 0 |
后面匹配到不同的字符时，就可以凭借前缀表快速找到已匹配部分的最长相同前后缀长度是什么。如下图所示，当匹配到 e ≠ f 时，此时pattern的指针指向索引 5 ，那么根据[0,5)，可以在前缀表立刻找到aabaa的最长相同前后缀长度为 2 。
则下一步，直接将pattern的指针指向最长相同前后缀长度 2 ，即指向 b
OK，讲了这么多，也知道 前缀表 的作用是什么了，那么如何记录和填充前缀表呢？
前缀表存储
关于记录前缀表，直接使用一个 int 数组即可，将这个数组命名为 next ，如下图所示：
前缀表填充
前缀表填充逻辑如下：
- 初始化：
next[0] = 0，此时子串只有一个字符，不存在前缀和后缀，因此最长相同前后缀长度为 0 。再定义两个指针，i表示当前字符的位置，j表示尝试前缀的末尾位置。i初始化为 1 ，因为next[0] = 0，直接从 1 开始填充即可。j初始化为 0 ，因为i = 1时，子串的前缀只有第 0 个字符，只能尝试将 0 个字符作为前缀。
- 遍历模式串：从
i = 1开始，逐个字符计算next[i]。 - 匹配：
- 如果
pattern[i] == pattern[j]，说明当前字符与尝试前缀字符匹配。next[i] = j + 1（为啥是j+1，例如aa，此时j=0，但是共同前后缀长度是 1 ）。- 然后
i和j都向后移动，即i++、j++。
- 如果
pattern[i] != pattern[j]，说明当前字符与前缀字符不匹配- 回退
j到next[j-1]，再重新比较pattern[i]和pattern[j]。直到j回退到0或找到匹配的前缀。 - 为什么回退到
next[j-1]？因为next[j-1]表示的是已匹配部分的最长相同前后缀长度，回退就是想看看将前缀缩短为上一次匹配成功的共同前后缀，因为有可能共同前后缀还是有效的，如果不理解，看后面的演示案例。
- 回退
- 如果
- 不匹配情况：如果
j回退到0，说明没有匹配的前后缀，next[i] = 0，然后i向后移动。 - 重复步骤3和4，直到遍历完整个模式串。
【案例】
初始化 next[0] = 0
① 初始化 i=1，j=0。
pattern[i]=pattern[j]=a，即前缀a等于后缀a，next[i]=++j=1
- 因为
pattern[i]=pattern[j]，i++, j++
② i=2，j=1。
pattern[i]!=pattern[j]，即前缀aa不等于后缀ab，把前缀缩短，j=next[j-1]=0
pattern[i]!=pattern[j]，即前缀a不等于后缀b，因为 j 已经走到 0 ，next[i]=0
- 因为
pattern[i]!=pattern[j]，只让 i++
③ i=3，j=0。
pattern[i]=pattern[j]=‘a’，即前缀a等于后缀a，next[i]=++j=1
- 因为
pattern[i]=pattern[j]，i++, j++
④ i=4，j=1。
pattern[i]=pattern[j]=‘a’，即前缀aa等于后缀aa，next[i]=++j=2
- 因为
pattern[i]=pattern[j]，i++, j++
④ i=5，j=2。
pattern[i]!=pattern[j]，即前缀aab不等于后缀aaf，把尝试前缀缩短，j=next[j-1]=1
pattern[i]!=pattern[j]，即前缀aa不等于后缀af，把前后缀缩短，j=next[j-1]=0
pattern[i]!=pattern[j]，即前缀a不等于后缀f，把前后缀缩短，j 已经走到 0 ，next[i]=0
【案例】
再举一个例子，看看为什么要将j回退到next[j-1]？
next[j-1]表示的是已匹配部分的最长相同前后缀长度，回退就是想看看将前缀缩短为上一次匹配成功的共同前后缀，现在看看还生不生效，其实也是利用前面的信息进行贪心的做法。
如下图所示：
b!=a，将j回退为next[j-1]=1，这样很快就可以得到最长相同前后缀是aa，而不是直接将j回退到 0 重新开始寻找最长相同前后缀。
next 数组填充代码实现
知道上面的逻辑之后，代码就很容易实现了
char[] patternCharArray = pattern.toCharArray();
int patternLen = pattern.length();
计算 next 数组
int[] next = new int[patternLen];
int j = 0;
for (int i = 1; i < patternLen; i++) {
while (true) {
if (patternCharArray[i] == patternCharArray[j]) {
// --if-- 如果pattern[i] == pattern[j]，说明当前字符与前缀字符匹配
next[i] = j + 1;
// i++ 已经在 for 循环中实现了
j++;
break;
} else {
// --if-- 如果pattern[i] != pattern[j]，说明当前字符与前缀字符不匹配
if (j == 0) {
// 本来就是0，不用设置
// next[i] = 0;
break;
}
// 回退j到next[j-1]
j = next[j - 1];
}
}
}
KMP搜索
得到了 next 数组之后，剩下的代码就更好写了，逻辑如下：
双指针遍历：
index1遍历主字符串，index2遍历模式字符串。
尝试匹配 text[index1] 和 pattern[index2]
-
匹配成功：
- 字符匹配时，双指针同时前进。
- 若
index2走完模式串，返回匹配的起始位置index1 - patternLen + 1。
-
匹配失败：
- 若
index2为 0，主指针index1前进。 - 否则，
index2回退到next[index2 - 1]继续匹配。
- 若
最终代码实现
public static int strStr(String text, String pattern) {
char[] textCharArray = text.toCharArray();
char[] patternCharArray = pattern.toCharArray();
int patternLen = pattern.length();
if (patternLen > textCharArray.length) {
// pattern 比 text 还长，直接返回-1
return -1;
}
计算 next 数组
int[] next = new int[patternLen];
int j = 0;
for (int i = 1; i < patternLen; i++) {
while (true) {
if (patternCharArray[i] == patternCharArray[j]) {
// --if-- 如果pattern[i] == pattern[j]，说明当前字符与前缀字符匹配
next[i] = j + 1;
// i++ 已经在 for 循环中实现了
j++;
break;
} else {
// --if-- 如果pattern[i] != pattern[j]，说明当前字符与前缀字符不匹配
if (j == 0) {
// 本来就是0，不用设置
// next[i] = 0;
break;
}
// 回退j到next[j-1]
j = next[j - 1];
}
}
}
查找 pattern 位置
int index1 = 0, index2 = 0;
while (index1 < textCharArray.length) {
if (textCharArray[index1] == patternCharArray[index2]) {
// --if-- 如果当前字符匹配，两个指针都前进
index1++;
index2++;
if (index2 == patternLen) {
// --if-- pattern的字符已经匹配完，返回索引（因为这里 index1++ 才-patternLen ，所以不用+1）
return index1 - patternLen;
}
} else {
if (index2 == 0) {
// --if-- pattern 指针已经归零，无法再回退了
index1++;
continue;
}
// 回退 pattern 指针
index2 = next[index2 - 1];
}
}
return -1;
}
时间复杂度O(n+m)
假设n为text长度，m为pattern长度，在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)。除此之外，还生成next数组，时间复杂度是O(m)