kmp

28. 找出字符串中第一个匹配项的下标

• 参考：https://www.bilibili.com/video/BV1AY4y157yL/?spm_id_from=333.337.search-card.all.click&vd_source=f3db174696f8b36e59e1b4a8fafeea5f
• 遍历法
• kmp

class Solution:
    # def strStr(self, haystack: str, needle: str) -> int:
    #     l_t = len(needle)
    #     for i in range(len(haystack)):
    #         if i+l_t > len(haystack):
    #             break
    #         if haystack[i:i+l_t] == needle:
    #             return i
    #     return -1
    
    # kmp
    def strStr(self, haystack: str, needle: str) -> int:
        next_list = self.get_next(needle)
        # print(needle,next_list)

        i = 0
        j = 0 
        while i < len(haystack) and j<len(needle):
            if haystack[i] == needle[j]:
                i+=1
                j+=1
            elif j>0:
                j = next_list[j-1]
            else:
                i+=1
            
            if j == len(needle):
                return i-j
        return -1
    
    def get_next(self,needle):
        next_list = [0]
        prefix_len = 0
        i = 1
        while i<len(needle):
            if needle[prefix_len] == needle[i]:
                prefix_len +=1
                next_list.append(prefix_len)
                i+=1
            else:
                if prefix_len == 0:
                    next_list.append(0)
                    i += 1
                else:
                    prefix_len = next_list[prefix_len-1]
        return next_list