kmp

28. 找出字符串中第一个匹配项的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
# def strStr(self, haystack: str, needle: str) -> int:
# l_t = len(needle)
# for i in range(len(haystack)):
# if i+l_t > len(haystack):
# break
# if haystack[i:i+l_t] == needle:
# return i
# return -1

# kmp
def strStr(self, haystack: str, needle: str) -> int:
next_list = self.get_next(needle)
# print(needle,next_list)

i = 0
j = 0
while i < len(haystack) and j<len(needle):
if haystack[i] == needle[j]:
i+=1
j+=1
elif j>0:
j = next_list[j-1]
else:
i+=1

if j == len(needle):
return i-j
return -1

def get_next(self,needle):
next_list = [0]
prefix_len = 0
i = 1
while i<len(needle):
if needle[prefix_len] == needle[i]:
prefix_len +=1
next_list.append(prefix_len)
i+=1
else:
if prefix_len == 0:
next_list.append(0)
i += 1
else:
prefix_len = next_list[prefix_len-1]
return next_list