From LeetCode 28. Implement strStr()
Description
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().
Solution
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