動機

複習kmp

Problem

Implement strStr().

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

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

 

Example 1:

Input: haystack = hello, needle = llOutput: 2

Example 2:

Input: haystack = aaaaa, needle = bbaOutput: -1

Example 3:

Input: haystack = , needle = Output: 0

 

Constraints:

  • 0 <= haystack.length, needle.length <= 5 * 104
  • haystack and needle consist of only lower-case English characters.

Sol

class Solution:
    def strStr(self, s: str, p: str) -> int:
        @cache
        def fail(i):
            if i <= 0:
                return 0
            else:
                j = fail(i-1)
                while j > 0 and p[j] != p[i]:
                    j = fail(j-1)
                return j+(1 if p[j] == p[i] else 0)
        i,j,n,m = 0,0,len(s),len(p)
        while i < n:
            if j == m:
                return i-m
            elif s[i] == p[j]:
                i += 1
                j += 1
            elif j == 0:
                i += 1
            else:
                j = fail(j-1)
                
        return n-m if j == m else -1