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

Solution 1: Brute-Force

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)
        for idxStart in range(n - m + 1):
            for idxNeedle in range(m):
                if haystack[idxStart + idxNeedle] != needle[idxNeedle]:
                    break
                elif (idxNeedle == m - 1): # and haystack[idxStart + idxNeedle] == needle[idxNeedle]
                    return idxStart
        return -1

Time Complexity: O(N*M)
Space Complexity: O(1)

Solution 2: KMP

Time Complexity: O(N)
Space Complexity: O(M)

Reference

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/12807/elegant-java-solution/
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/12956/c-brute-force-and-kmp/?orderBy=most_votes

https://medium.com/nlp-tsupei/kmp%E7%AE%97%E6%B3%95%E8%A9%B3%E8%A7%A3-1b1050a45850

Follow-up 1: 459. Repeated Substring Pattern

Follow-up 2: 686. Repeated String Match