刷题笔记:力扣第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; // 字符不匹配跳出第二层循环换 i1 重试 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.本题最优的解法为KMPKnuth-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算法十分精妙具体原理建议看网上讲解视频后面再遇到类似题目的时候要多加练习。