Leetcode daily question - 28 Implement strstr() (simple)

String matching problem ： There are generally two methods ： Violence matching method and kmp Algorithm

Method 1 ： Violence solution

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        haystack_length = len(haystack)
        needle_length = len(needle)
        i = 0
        while i+needle_length <= haystack_length:
            flag = True
            for j in range(0,needle_length):
                if haystack[i+j] != needle[j]:
                    flag = False
                    break
            if flag:
                return i        
            i += 1
        return -1
        # Adapted from the official java Code 

Time limit exceeded , Maybe the last instance is too long .

Method 2 ：kmp Algorithm

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        a=len(needle)
        b=len(haystack)
        if a==0:
            return 0
        next=self.getnext(a,needle)
        p=-1
        for j in range(b):
            while p>=0 and needle[p+1]!=haystack[j]:
                p=next[p]
            if needle[p+1]==haystack[j]:
                p+=1
            if p==a-1:
                return j-a+1
        return -1

    def getnext(self,a,needle):
        next=['' for i in range(a)]
        k=-1
        next[0]=k
        for i in range(1,len(needle)):
            while (k>-1 and needle[k+1]!=needle[i]):
                k=next[k]
            if needle[k+1]==needle[i]:
                k+=1
            next[i]=k
        return next
        # This code refers to 「 Random code recording 」

Such a classic kmp The algorithm is really brain - burning , So I decided to write a separate article kmp Summary of the algorithm