動機
複習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
andneedle
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