Brute Force

function strStr(haystack: string, needle: string): number {
    const [hlen, nlen] = [haystack.length, needle.length];
    for (let i = 0; i <= hlen - nlen; i++) {
        for (let l = 0; l <= nlen - 1; l++) {
            if (haystack[i + l] !== needle[l]) break;
            if (l === nlen - 1) return i;
        }
    }
    return -1;
};

KMP

• LPS (Longest Prefix Suffix) Array
• lps[i] 表示 needle[0:i] 这个子串中，最长的相等的 Prefix 和 Suffix 的长度, 前缀和后缀都不能包含整个字符串自己

function strStr(haystack: string, needle: string): number {
    const n = haystack.length;
    const m = needle.length;
    if (m === 0) return 0;

    // Step 1: build LPS table
    const lps = new Array(m).fill(0);
    let pre = 0;
    for (let i = 1; i < m; i++) {
        while (pre > 0 && needle[i] !== needle[pre]) {
            pre = lps[pre - 1];
        }
        if (needle[pre] === needle[i]) {
            pre++;
            lps[i] = pre;
        }
    }

    // Step 2: search using LPS
    for (let i = 0, j = 0; i < n;) {
        if (haystack[i] === needle[j]) {
            i++; j++;
            if (j === m) return i - j; // full match
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }

    return -1;
};