KMP算法解決的問題：
KMP算法解決字符串匹配問題干毅，給兩個字符串循未，查找其中一個字符串是否包含另一個字符串，如果包含搏存，返回包含的起始位置
時間復雜度為 o(m+n)
KMP偽代碼
- 在串S和串T中分別設(shè)比較的起始下標i和j
- 如果S和T的的所有字符未比較完瑰步，則循環(huán)
2.1 如果S[i] == T[j],繼續(xù)比較S和T的下一個字符
2.2 否則將j滑向next[j]的位置，即 j = next[j]
2.3 如果j == -1,則將i和j分別+1璧眠，準備下一趟比較 - 如果T中的字符串均比較完畢缩焦，則返回匹配的起始下標，否則返回-1
next數(shù)組求解
image.png
next數(shù)組的兩種求解方式
直接插入-1法
懶貓老師-數(shù)據(jù)結(jié)構(gòu)-(15)KMP算法2-next數(shù)組(模式匹配,字符串匹配)
n = len(needle)
prefixArr = [0] * n
j = -1
i = 0
prefixArr[0] = -1
while i < n - 1:
if j == -1 or needle[j] == needle[i]:
j += 1
i += 1
prefixArr[i] = j
else:
j = prefixArr[j]
直接插入-1法 感想
移位插入-1法
KMP字符串匹配算法
三哥講解KMP算法part1
三哥講解KMP算法part2之尋找前綴的方法
n = len(needle)
prefixArr = [0] * len(needle)
j = 0
i = 1
while i < n:
if needle[j] == needle[i]:
j += 1
prefixArr[i] = j
i += 1
else:
if j > 0:
j = prefixArr[j - 1]
else:
prefixArr[i] = j
i += 1
prefixArr.insert(0,-1)
prefixArr.pop()
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
m = len(haystack)
n = len(needle)
if m == 0 and n == 0 or n == 0:
return 0
i = 0
j = 0
nextArr = self.prefixArr(needle)
while i < m and j < n:
if j == n - 1 and haystack[i] == needle[j]:
return i - j
if j == -1 or haystack[i] == needle[j]:
j += 1
i += 1
else:
j = nextArr[j]
return -1
def prefixArr(self, s:str) -> list:
j = -1
i = 0
n = len(s)
nextArr = [0] * n
nextArr[0] = j
while i < n - 1:
if j == -1 or s[i] == s[j]:
j += 1
i += 1
nextArr[i] = j
else:
j = nextArr[j]
return nextArr
