首页 > itarticle > kmp

kmp

admin 11月 14, 2020 0

Description

1
2
3

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Solution

The brute force is very easy to come up with, and the time complexity will be O(mn)

However, we can implement kmp to get O(n + m).
https://www.youtube.com/watch?v=BXCEFAzhxGY

class :
    def strStr(self, s: str, p: str) -> int:
        if p == '': return 0
        
        n, m = len(s), len(p)
        # prepare a prefix - suffix array for p
        kmp = [0] * m
        i, l = 1, 0
        while i < m:
            if p[i] == p[l]:
                l += 1
                kmp[i] = l
                i += 1
            else:
                if l > 0: l = kmp[l - 1]
                else: i += 1

        # traverse the s
        i, j = 0, 0
        while i < n:
            if s[i] == p[j]:
                j += 1
                i += 1
                if j == m: return i - j
            else:
                if j > 0: j = kmp[j - 1]
                else: i += 1
        return -1

kmp array is the longest prefix - suffix array of pattern string.
For example:
String:    'abaaababcd'
kmp array: [0011121200]
By using kmp array, once we find that s[i] != p[j], j = kmp[j - 1] instead of 0