KMP- 简单的子串匹配

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

问题描述

输入文本串haystack，和模式串needle,找到文本串中是否存在模式串，若存在输出第一次出现的位置，否则输出-1
例子：输入:haystack=“hello”, needle = “ll”; 输出：2
例子：输入:haystack=“hello”, needle = “aa”; 输出：-1

思路

1. 暴力搜索:

遍历haystack的每个长度为m的子串，判断它和needle是否相等，其中m是指needle的长度。为加快搜索，在遍历子串和needle第i个位置时若不相等，可以提前退出比较；时间复杂度O(n*m), 空间复杂度O(1)

2. KMP

为加快搜索，可以先构造模式串needle的前缀表pres，其中前缀表表示该字符串各位置处相等的后缀和前缀最长长度，为方便计算，将pres的i+1位置表示字符串i位置的最长相等前缀后缀长度。最后在实现搜索haystack中needle时。定义两个指针分别从haystack和needle中出发，直到发现不一样的位置，根据pres表快速将j指针回退到下一个可以匹配的位置上，这个位置正好使得needle的j位置前字串和haystack的i位置同长的子串相等，若无该位置，则i，j各往前走一步。如此下去，直到i，j超出范围，由于计算pres需要遍历一次needle，且每次操作可认为只有常数次操作，匹配时同样只需遍历一次haystack,且每次操作只有常数次计算，所以总共时间复杂度为O(n+m),空间复杂度O(m)

复杂度

时间复杂度:

暴力：$O(n?m)$
KMP : $O(n+m)$

空间复杂度:

暴力：$O(1)$
KMP $O(m)$

Code

暴力搜索

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

KMP

class Solution:
    def strStr(self, haystack: str, needle: str) ->  int:
        def get_next(str1):
            n = len(str1)
            pres = [-1] * (n +1)
            for i in range(n):
                t = pres[i]
                while str1[i] != str1[t] and t!=-1:
                    t = pres[t]
                pres[i+1] = t + 1 
            return pres
        
        i, j = 0, 0
        pres = get_next(needle)
        while j<len(needle) and i<len(haystack):
            while not haystack[i] == needle[j] and j!=-1:
                j = pres[j]
            i += 1
            j += 1
        if j==len(needle):
            return i-len(needle)
        return -1