给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1
方法一：暴力匹配法
暴力匹配法的思路是从 haystack 的第一个字符开始，依次与 needle 的字符进行比较，如果在某一位置不匹配，则将 haystack 的比较起始位置后移一位，重新开始比较，直到找到匹配的子串或者遍历完 haystack。
function strStr(haystack: string, needle: string): number {const m = haystack.length;const n = needle.length;for (let i = 0; i <= m - n; i++) {let j;for (j = 0; j < n; j++) {if (haystack[i + j]!== needle[j]) {break;}}if (j === n) {return i;}}return -1;
}// 示例调用
const haystack = "sadbutsad";
const needle = "sad";
const result = strStr(haystack, needle);
console.log("第一个匹配项的下标:", result);
复杂度分析
- 时间复杂度：O((m-n+1)xn)，其中 m 是
haystack的长度，n 是needle的长度。在最坏情况下，对于haystack中每个长度为 n 的子串，都需要比较 n 次字符。 - 空间复杂度：O(1)，只使用了常数级的额外空间。
方法二：KMP 算法
KMP 算法的核心是利用已经匹配的部分信息，避免不必要的重复比较。通过预处理 needle 字符串，得到一个部分匹配表（也称为前缀函数），在匹配过程中根据部分匹配表来移动 needle 的位置。
function computePrefix(needle: string): number[] {const n = needle.length;const lps = new Array(n).fill(0);let len = 0;let i = 1;while (i < n) {if (needle[i] === needle[len]) {len++;lps[i] = len;i++;} else {if (len!== 0) {len = lps[len - 1];} else {lps[i] = 0;i++;}}}return lps;
}function strStr(haystack: string, needle: string): number {const m = haystack.length;const n = needle.length;const lps = computePrefix(needle);let i = 0;let j = 0;while (i < m) {if (needle[j] === haystack[i]) {i++;j++;}if (j === n) {return i - j;} else if (i < m && needle[j]!== haystack[i]) {if (j!== 0) {j = lps[j - 1];} else {i++;}}}return -1;
}// 示例调用
const haystack2 = "leetcode";
const needle2 = "leeto";
const result2 = strStr(haystack2, needle2);
console.log("第一个匹配项的下标:", result2);
复杂度分析
- 时间复杂度：O(m+n)，其中 m 是
haystack的长度，n 是needle的长度。预处理needle字符串得到部分匹配表的时间复杂度为 O(n) ，在haystack中进行匹配的时间复杂度为 O(m)。 - 空间复杂度：O(n)，主要用于存储部分匹配表
lps，其长度为needle的长度 n 。
综上所述，暴力匹配法实现简单，但时间复杂度较高；KMP 算法虽然实现相对复杂，但时间复杂度较低，适用于处理较长的字符串。
