KMP算法用于检查短字符串是否在某个长字符串中。
算法过程
使用kmp解LeetCode28题
#
# [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