LC28 Implement strStr()

"""
main idea: use string == string2 comparison. since target string is fixed(needle) => length already know. all we need to do is to loop through string1, each index check start from current index to length of needle, if it's same as needle 
edge case: needle = '' ; optimization: len(haystack) < len(needle), can terminate early
"""
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # time O(N*M) space O(1)
        if not needle:
            return 0
        if len(haystack) < len(needle):
            return -1
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

class Solution:
    def strStr(self, txt: str, p: str) -> int:
        """ tc O(len(txt) + len(p))  sc O(p)
        main idea: KMP
        1. build table for p 
        2. loop through txt with reference of p,  check if pointer in p can reach the end 
        """
        if not p: return 0
        nxt = [0] * len(p)
        i,j = 0,1
        while j < len(p):
            if p[i] == p[j]:
                nxt[j] = i + 1
                i += 1 
                j += 1 
            elif i > 0:
                i = nxt[i-1]
            else:
                j += 1 
    
        i = 0
        j = 0
        while j < len(txt):
            if txt[j] == p[i]:
                j += 1
                i += 1
            elif i > 0 :
                i = nxt[i-1]
            else:
                j += 1 
            if i == len(p): return j - len(p)
        return -1