Find the Index of the First Occurrence in a String

Given two strings haystack and needle, return the index of the first occurrence of needle in haystack.

If needle does not occur in haystack, return:

-1

Example

Input:

haystack = "sadbutsad"

needle = "sad"

The first occurrence of "sad" starts at index 0.

Output

0

Main Idea

We need to check every possible starting position in haystack.

For each position:

1. Check whether there are enough characters remaining.
2. Compare the substring starting at that position with needle.
3. If all characters match, return that index.
4. If no position matches, return -1.

Example

haystack = "hello"

needle   = "ll"

Check:

h e → no

e l → no

l l → match

Therefore:

Answer = 2

Important Point

We need the first occurrence, so we return immediately when a match is found.