KMP算法

KMP算法用于检查短字符串是否在某个长字符串中。

算法过程

KMP

使用kmp解LeetCode28题

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#
# [28] Implement strStr()
#
# https://leetcode.com/problems/implement-strstr/description/
#
# algorithms
# Easy (29.86%)
# Total Accepted: 316K
# Total Submissions: 1.1M
# Testcase Example: '"hello"\n"ll"'
#
# Implement strStr().
#
# Return the index of the first occurrence of needle in haystack, or -1 if
# needle is not part of haystack.
#
# Example 1:
#
#
# Input: haystack = "hello", needle = "ll"
# Output: 2
#
#
# Example 2:
#
#
# Input: haystack = "aaaaa", needle = "bba"
# Output: -1
#
#
# 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().
#
#
class Solution:
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if not needle:
return 0
h_length, n_length = len(haystack), len(needle)
if h_length < n_length:
return -1

next_arr = self.get_next_arr(needle)
i = j = 0
while i < h_length and j < n_length:
if haystack[i] == needle[j]:
i += 1
j += 1
elif next_arr[j] == -1:
i += 1
else:
j = next_arr[j]

return i - j if j == n_length else -1

def get_next_arr(self, needle):
length = len(needle)
if length < 2:
return [-1]

next_arr = [0 for i in range(length)]
next_arr[0], next_arr[1] = -1, 0
i, cur = 2, 0
while i < length:
if needle[cur] == needle[i-1]:
next_arr[i] = cur + 1
cur = next_arr[i]
i += 1
elif cur > 0:
cur = next_arr[cur]
else:
next_arr[i] = 0

return next_arr
  • 本文作者: 大护法
  • 本文链接: https://todebug.com/kmp/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 4.0 许可协议。转载请注明出处!
0%