LC28. Find the Index of the First Occurrence in a String

Approach 1: Sliding Window

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        nlen = len(needle)
        hlen = len(haystack)
 
        for i in range(hlen - nlen + 1):
            for j in range(nlen):
                if haystack[i + j] != needle[j]:
                    break
                
                if j == nlen - 1:
                    return i
        
        return -1

Complexity

Time: $O(n\ast h)$
Space: $O(1)$

Approach 2: KMP

TODO

Approach 3: Z-algorithm

TODO

Approach 4: Two-way string matching

TODO

Other Languages