Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Link to leetcode

Solution

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */

var strStr = function (txt, pattern) {

    const prefixTable = computePrefix(pattern);

    let i = 0, j = 0;

    while (i < txt.length && j < pattern.length) {
        if (txt[i] === pattern[j]) {
            i++;
            j++;
        }

        else if (j > 0) {
            j = prefixTable[j - 1];
        }

        else {
            i++;
        }
    }

    return j === pattern.length ? i - j : -1;
}

function computePrefix(pattern) {

    let len = 0;
    let lps = [0];
    let i = 1;

    while (i < pattern.length) {

        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        }

        else if (len !== 0) {            
            len = lps[len - 1];
        }

        else {
            lps[i] = 0;
            i++;
        }
    }

    return lps
}