题目描述

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

示例 1：

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

算法思路

其实这题还不用写也可以看出来是典型的KMP题目，如果直接调用strStr()函数就没意思了，但是我在之前总是习惯于逃避，所有“面试不手撕”的题目我都会选择逃避，以至于前阵子我在复习数据结构的时候，看见KMP就直接翻过去了。今天复习算法，再次遇到KMP，我决定还是做一做，万一呢？

第一步：求Next数组

我一直知道这个next数组是什么意思：它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。，但是从来没有深究过他是怎么求出来的，于是我今天跟着代码随想录老是敲了一遍代码，理解了它的由来，首先需要一点前置知识：最长相等前后缀。

  • 对于字符串"aabaa"，其前缀规定为：以首字母开头且不含最后一个字母的子串，比如"a","aa","aab",...；相应的，其后缀就为"a","aa","baa",...。
  • 最长相等前后缀，就是前后缀中最长的相等部分的长度，如上就是"aa"，长度为2。

对于模式串，需要从下标0~n-1求出对应的next[i]，组成next数组，其中的next[i]可以是s[0~i]的最长相等前后缀，如图所示(有点懒，借用的卡哥的图)：

image-20250714214305987

接着编写代码实现获取next数组，当然我觉得这个数组的获取方式有很多，网站上给的也需要逻辑上的思考，我建议使用”aabaaf”做一个尝试即可，然后在理解原理的基础上背下来这个板子即可，不需要过多深究：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void getNext(vector<int> &next, const string& s) {
    int j = -1;
    next[0] = j;

    for (int i = 1; i < s.length(); i++) {
        while (j >= 0 && s[i] != s[j + 1]) {
            // 前后缀不匹配
            j = next[j]; 
        }

        if (s[i] == s[j + 1]) {
            j++;
        }
        next[i] = j;
    }
}

第二步：KMP匹配

接下来就比较简单了，因为我觉得大家包括我不会KMP的很大的问题就是不知道NEXT数组怎么求，如果知道next数组的用法、再加上如何求解的话，我觉得是很简单的，只需要挨个匹配，当出现不相等时，将模式串的下标j移动到next[j]即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int strStr(string haystack, string needle) {
      if (needle.length() == 0) {
          return 0;
      }

      vector<int> next(needle.size()); // next数组
      getNext(next, needle);
      int j = -1;
      for (int i = 0; i < haystack.size(); i++) {
          while (j >= 0 && haystack[i] != needle[j + 1]) {
              j = next[j];
          }

          if (haystack[i] == needle[j + 1]) { // 匹配
              j++;
          }

          if (j == (needle.length() - 1)) {
              return (i - needle.length() + 1);
          }
      }
      return -1;
  }

哎实在是比较懒，只想自己动手做做笔记，实在没办法写出优质教程，如果你不小心看到这个lj博客，还是没看明白的话，就去看看卡哥的笔记，我觉得非常清楚，网址奉上：

碎碎念

哎简直不敢相信我竟然真的夏0营了，上交进不去在我意料之中，也算是和曾经的梦校彻底告别了，研究生也没去成，估计这辈子也没几次机会了；但是科大人大我竟然也没进啊！真的不想留本校唉唉唉……希望弱鸡学生遇上心软华五。