LC 0028 [E] Implement strStr() - ALawliet/algorithms GitHub Wiki

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1
    
    def strStr(self, haystack, needle):
        def kmp(str_): # O(n)
            b, prefix = 0, [0]
            for i in range(1, len(str_)):
                while b > 0 and str_[i] != str_[b]:
                    b = prefix[b - 1]
                if str_[b] == str_[i]:
                    b += 1
                else:
                    b = 0
                prefix.append(b)
            return prefix

        str_ = kmp(needle + '#' + haystack)
        n = len(needle)
        if n == 0:
            return n
        for i in range(n + 1, len(str_)):
            if str_[i] == n:
                return i - 2 * n
        return -1
    
    def strStr(self, haystack, needle):
        if needle not in haystack:
            return -1
        return haystack.index(needle)
    
    def strStr(self, haystack, needle):
        return haystack.find(needle)