# 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.
``````

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 = ;
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
}
``````

I hope this post was helpful to you.

Leave a reaction if you liked this post!