LeetCode 面试经典 150_数组/字符串_找出字符串中第一个匹配项的下标（23_28_C++_简单）(KMP 算法)

题目描述：

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

输入输出样例：

示例 1：
输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：
输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

提示：
1 <= haystack.length, needle.length <= 10⁴
haystack 和 needle 仅由小写英文字符组成

题解：

解题思路：

思路一（暴力破解）：

1、从左往右进行核对，找出 needle 字符串的第一个匹配项的下标。如果 needle 不是 haystack 的一部分，则返回 -1。

2、复杂度分析：
① 时间复杂度：O(n×m)，其中 n 是字符串 haystack 的长度，m 是字符串 needle 的长度。最坏情况下我们需要将字符串 needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。
② 空间复杂度：O(1)。

思路二（KMP 算法）：

1、next 数组用于存储每个位置的最长前缀后缀匹配长度。这样在匹配过程中，如果出现不匹配的情况，可以利用这个数组跳过一些无效的比较。

例：主串：abababcaa ，子串：ababc
next=[0,0,1,2,0]
abababcaa
ababc          下标为4，通过next[4-1] = 2 来跳转下标 。
abababcaa
    ababc

ababc 的前缀为 a,ab,aba,abab。后缀为 c,bc,abc,babc。
next 数组是对子串进行的处理。
① a无前后缀 ，next[0]=0；
② ab 前缀 a，后缀 b 不匹配，next[1]=0；
③ aba 最长匹配前缀 a，最长匹配后缀 a ,next[2]=1；
④ abab 最长匹配前缀 ab ,最长匹配后缀 ab ,next[3]=2；
⑤ ababc 无匹配前后缀，next[4]=0；

感觉这个博主的 kmp 讲的比较好（点击跳转）

2、复杂度分析
① 时间复杂度：O(n+m)，其中 n 是字符串 haystack 的长度，m 是字符串 needle 的长度。我们至多需要遍历两字符串一次。
② 空间复杂度：O(m)，其中 m 是字符串 needle 的长度。next数组。

代码实现

代码实现（思路一（暴力破解））：

class Solution1 {
public:int strStr(string haystack, string needle) {// 如果 needle 比 haystack 长，直接返回 -1if (needle.size() > haystack.size()) return -1;// 计算 haystack 剩余的长度，最多能够开始匹配的次数int count = haystack.size() - needle.size() + 1;// 遍历 haystack 中的每个起始位置for (int haystack_index = 0; haystack_index < count; haystack_index++) {int haystack_ptr = haystack_index;  // haystack 的指针int needle_ptr = 0;   // needle 的指针// 如果 haystack 和 needle 的当前字符相等，则继续比较下一个字符while (needle_ptr < needle.size() && haystack[haystack_ptr] == needle[needle_ptr]) {haystack_ptr++;  // haystack 的指针向后移动needle_ptr++;    // needle 的指针向后移动}// 如果 needle 完全匹配，返回 haystack_indexif (needle_ptr == needle.size()) {return haystack_index;}}// 如果没有找到匹配，返回 -1return -1;}
};

代码实现（思路二（KMP 算法））：

class Solution2 {
public:int strStr(string haystack, string needle) {int n = haystack.size(), m = needle.size();  // 获取haystack和needle的长度// 如果needle为空，返回0，根据题意要求if (m == 0) {return 0;}vector<int> next(m);  // 用来存储needle的"部分匹配表"// 计算next数组，next数组表示的是子串中每个位置的最长前后缀匹配的长度// next[i]表示needle[0..i]的最长前后缀匹配的长度for (int i = 1, j = 0; i < m; i++) {  // i从1开始，因为next[0]默认是0// 如果字符不匹配，回溯j指针，利用已计算的next数组避免重新比较while (j > 0 && needle[i] != needle[j]) {j = next[j - 1];  // 回溯到next[j-1]的位置}// 如果字符匹配，移动j指针if (needle[i] == needle[j]) {j++;}// 记录当前的部分匹配长度next[i] = j;}// 接下来用next数组在haystack中进行匹配// i遍历haystack，j遍历needlefor (int i = 0, j = 0; i < n; i++) {// 如果haystack[i]和needle[j]不匹配，回溯jwhile (j > 0 && haystack[i] != needle[j]) {j = next[j - 1];  // 回溯到next[j-1]的位置}// 如果匹配，继续比较下一个字符if (haystack[i] == needle[j]) {j++;}// 如果j到达needle的末尾，表示找到了匹配的子串if (j == m) {return i - m + 1;  // 返回匹配位置的起始下标}}// 如果匹配失败，返回-1return -1; }
};

以思路一为例进行调试

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;class Solution1 {
public:int strStr(string haystack, string needle) {// 如果 needle 比 haystack 长，直接返回 -1if (needle.size() > haystack.size()) return -1;// 计算 haystack 剩余的长度，最多能够开始匹配的次数int count = haystack.size() - needle.size() + 1;// 遍历 haystack 中的每个起始位置for (int haystack_index = 0; haystack_index < count; haystack_index++) {int haystack_ptr = haystack_index;  // haystack 的指针int needle_ptr = 0;   // needle 的指针// 如果 haystack 和 needle 的当前字符相等，则继续比较下一个字符while (needle_ptr < needle.size() && haystack[haystack_ptr] == needle[needle_ptr]) {haystack_ptr++;  // haystack 的指针向后移动needle_ptr++;    // needle 的指针向后移动}// 如果 needle 完全匹配，返回 haystack_indexif (needle_ptr == needle.size()) {return haystack_index;}}// 如果没有找到匹配，返回 -1return -1;}
};int main(int argc, char const *argv[])
{string haystack="a";string needle= "a";Solution1 s;cout<<s.strStr(haystack,needle)<<endl;return 0;
}

LeetCode 面试经典 150_数组/字符串_找出字符串中第一个匹配项的下标（23_28)原题链接
欢迎大家和我沟通交流(✿◠‿◠)