力扣由浅至深每日一题.09找出字符串中第一个匹配项的下标

成败有时，不可丧志，山高路远，愿诸君扶摇直上

                                                          —— 24.3.20

 找出字符串中第一个匹配项的下标

给你两个字符串 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 <= 104haystack 和 needle 仅由小写英文字符组成 方法一 暴力匹配法

思路及算法

我们可以让字符串 needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1。

class Solution { public int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); for (int i = 0; i + m <= n; i++) { boolean flag = true; for (int j = 0; j < m; j++) { if (haystack.charAt(i + j) != needle.charAt(j)) { flag = false; break; } } if (flag) { return i; } } return -1; } } 方法二 Knuth-Morris-Pratt算法        KMP算法

思路及算法

KMP算法，先求出最长公共前后缀，然后通过KMP算法找出最长子串，然后判断是否存在最长子串，若子串全部都匹配，则返回匹配处的下标

力扣官方题解：

作者：宫水三叶 链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/575568/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution { // KMP 算法 // ss: 原串(string) pp: 匹配串(pattern) public int strStr(String ss, String pp) { if (pp.isEmpty()) return 0; // 分别读取原串和匹配串的长度 int n = ss.length(), m = pp.length(); // 原串和匹配串前面都加空格，使其下标从 1 开始 ss = " " + ss; pp = " " + pp; char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的） int[] next = new int[m + 1]; // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】 for (int i = 2, j = 0; i <= m; i++) { // 匹配不成功的话，j = next(j) while (j > 0 && p[i] != p[j + 1]) j = next[j]; // 匹配成功的话，先让 j++ if (p[i] == p[j + 1]) j++; // 更新 next[i]，结束本次循环，i++ next[i] = j; } // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】 for (int i = 1, j = 0; i <= n; i++) { // 匹配不成功 j = next(j) while (j > 0 && s[i] != p[j + 1]) j = next[j]; // 匹配成功的话，先让 j++，结束本次循环后 i++ if (s[i] == p[j + 1]) j++; // 整一段匹配成功，直接返回下标 if (j == m) return i - m; } return -1; } }