刷题笔记:力扣第28题-找出字符串中第一个匹配项的下标

1.拿到题目首先想到的就是暴力匹配法，遍历haystack字符串，当找到与needle第一个字符相同的字符时进入内部循环，判断后续的字符是否都匹配，如果匹配则返回下标值，如果不匹配则break，继续遍历。

2.基于以上思想，可写出完整代码如下：

1. int strStr(char* haystack, char* needle) { 2. int len1 = strlen(haystack); // 主串长度（长的那个） 3. int len2 = strlen(needle); // 模式串长度（短的那个） 4. 5. // 边界条件：模式串比主串还长，一定不可能匹配 → 返回 -1 6. if (len2 > len1){ 7. return -1; 8. } 9. 10. // 遍历主串，尝试每一个可能的起点 i 11. for (int i = 0; i < len1; i++){ 12. 13. // 剪枝：剩余长度不够了，直接返回 -1 14. // 含义：从 i 开始剩下的字符 < len2，肯定匹配不到 15. if (len1 – i < len2){ 16. return -1; 17. } 18. 19. // 只有当前字符等于 needle 的第一个字符，才进入第二层循环 20. if (haystack[i] == needle[0]){ 21. int j; 22. // 逐个比较后续字符 23. for (j = 1; j < len2; j++){ 24. if (haystack[i + j] != needle[j]){ 25. break; // 字符不匹配，跳出第二层循环，换 i+1 重试 26. } 27. } 28. // 如果 j 走到了 len2，说明全部字符都匹配上了 29. if (j == len2){ 30. return i; // 返回起始下标 i 31. } 32. } 33. } 34. 35. // 遍历完都没找到 36. return -1; 37. }

其中有两次边界判断，第一次if (len2 > len1)是排除待查找字符串比主字符串短的特殊情况，第二次if (len1 – i < len2)是为了进行边界剪枝，如果主字符串剩余长度小于待查找字符串长度则直接return -1。该算法的时间复杂度为O(N×M)，N和M分别为两个字符串的长度，空间复杂度为O(1)。

3.本题最优的解法为KMP（Knuth-Morris-Pratt）算法，它的原则是主字符串haystack的指针（i）永远不回退，一直往前走。当遇到不匹配的时候，KMP算法会根据已知的信息，把单词needle向右多滑动一点而不是只滑动一格。要想实现这个想法，需要用到pi数组，它记录了needle自己本身的对称性，具体来说就是“最长相同的前后缀长度”。当不匹配的时候，KMP算法会查看pi数组对应的值，直接跳到合适的位置继续进行匹配。

4.pi数组的相关代码如下，其中m为needle字符串的长度：

1. int pi[m]; 2. pi[0] = 0; // 第一个字符显然小抄是 0 3. 4. // i 是后缀的末尾，j 是前缀的末尾（同时也是当前相同部分的长度） 5. for (int i = 1, j = 0; i < m; i++) { 6. 7. // 【核心难点】：如果不匹配了怎么办？ 8. while (j > 0 && needle[i] != needle[j]) { 9. // j 退回到它上一个成功匹配的位置（查之前写好的小抄） 10. // 就像找备胎，当前备胎不行，就看看备胎的备胎行不行 11. j = pi[j - 1]; 12. } 13. 14. // 如果匹配上了 15. if (needle[i] == needle[j]) { 16. j++; // 相同部分的长度 + 1 17. } 18. 19. // 把当前算出来的长度写进小抄里 20. pi[i] = j; 21. }

使用pi数组的代码如下：

1. // i 是主串的指针（永远向前，不回退） 2. // j 是单词 needle 的指针（遇到不匹配就查小抄回退） 3. for (int i = 0, j = 0; i < n; i++) { 4. 5. // 发现不匹配！ 6. while (j > 0 && haystack[i] != needle[j]) { 7. // 主串指针 i 不动！ 8. // 单词指针 j 查小抄，看看应该把单词滑动到哪个位置继续比 9. j = pi[j - 1]; 10. } 11. 12. // 发现匹配上了 13. if (haystack[i] == needle[j]) { 14. j++; // 单词指针往下走一格 15. } 16. 17. // 如果 j 走到了单词的末尾，说明全匹配上了！ 18. if (j == m) { 19. // 返回起点的位置。当前在 i，单词长度是 m，所以起点是 i - m + 1 20. return i - m + 1; 21. } 22. }

该算法的时间复杂度为O(N + M)，是最优的解法。KMP算法十分精妙，具体原理建议看网上讲解视频，后面再遇到类似题目的时候要多加练习。