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

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

方法一：暴力匹配法

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 haystack1 = "sadbutsad";
const needle1 = "sad";
console.log(strStr(haystack1, needle1));

方法二：KMP 算法

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";
console.log(strStr(haystack2, needle2));

复杂度分析

1. 暴力匹配法：
   • 时间复杂度：\(O((m - n + 1) \times n)\)，其中 m 是 haystack 的长度，n 是 needle 的长度。在最坏情况下，对于 haystack 中每个长度为 n 的子串，都需要比较 n 次字符。
   • 空间复杂度：\(O(1)\)，只使用了常数级的额外空间。
2. KMP 算法：
   • 时间复杂度：\(O(m + n)\)，其中 m 是 haystack 的长度，n 是 needle 的长度。预处理 needle 字符串得到部分匹配表的时间复杂度为 \(O(n)\)，在 haystack 中进行匹配的时间复杂度为 \(O(m)\)。
   • 空间复杂度：\(O(n)\)，主要用于存储部分匹配表 lps，其长度为 needle 的长度 n。

暴力匹配法实现简单但效率较低，KMP 算法虽然实现相对复杂，但在处理较长字符串时效率更高。