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

Example 2:

``````Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
``````

Constraints:

• `1 <= haystack.length, needle.length <= 104`
• `haystack` and `needle` consist of only lowercase English characters.

KMP
Preprocess `needle` to generate the `longest_border` array
e.g.
`a b c d a b e e a b f`
`0 0 0 0 1 2 0 0 1 2 0`

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 `````` ``````class Solution: def strStr(self, haystack: str, needle: str) -> int: m = len(needle) n = len(haystack) if n < m: return -1 # == PREPROCESSING # longest border array longest_border = [0] * m # Length of Longest Border for prefix before it. prev = 0 # Iterating from index-1. longest_border[0] will always be 0 i = 1 while i < m: if needle[i] == needle[prev]: # Length of Longest Border Increased prev += 1 longest_border[i] = prev i += 1 else: # Only empty border exist if prev == 0: longest_border[i] = 0 i += 1 # Try finding longest border for this i with reduced prev else: prev = longest_border[prev - 1] # == SEARCHING # Pointer for haystack haystack_pointer = 0 # Pointer for needle. # Also indicates number of characters matched in current window. needle_pointer = 0 while haystack_pointer < n: if haystack[haystack_pointer] == needle[needle_pointer]: # Matched Increment Both needle_pointer += 1 haystack_pointer += 1 # All characters matched if needle_pointer == m: # m characters behind last matching will be window start return haystack_pointer - m else: if needle_pointer == 0: # Zero Matched haystack_pointer += 1 else: # Optimally shift left needle_pointer. # Don't change haystack_pointer needle_pointer = longest_border[needle_pointer - 1] return -1``````