next数组的意思就是 next[i] = len; 长度为i的数组的前缀和后缀相等的最大长度。 例如abcdabc就是 next[7] = 3; 相等的前缀和后缀最长是abc长度为3
next理解: KMP中的next数组，有的也称fail失败数组，存的到底是什么。是首子串和尾子串能匹配的最大长度
kmp
特意设置next[0] = -1, 因为当next[0]=0地时候会死循环，无限地j=next[j], j=0.
class Solution:
def getNext(self, s):
next = [-1 for _ in range(len(s))]
# 初始状态,i=0,j=-1,相等或者j==-1即+1，否则j回退。index 1的值0，index 0的值是-1.
i, j = 0, -1
while i < len(s) - 1:
if j == -1 or s[i] == s[j]:
i, j = i + 1, j + 1
next[i] = j
else:
j = next[j]
return next
def strStr(self, haystack: str, needle: str) -> int:
# 初始状态,i和j都是0，相等或者j==-1即+1，否则j回退。
if len(needle) == "":
return 0
i, j = 0, 0
next = self.getNext(needle)
while i < len(haystack) and j < len(needle):
if j == -1 or haystack[i] == needle[j]:
i, j = i + 1, j + 1
else:
j = next[j]
return i - j if j == len(needle) else -1
有p[j]==p[next[j]]的优化
def kmp_search(s=str(), p=str()):
next = get_next(p)
i, j = 0, 0
while i < len(s) and j < len(p):
if j == -1 or s[i] == p[j]:
i, j = i + 1, j + 1
else:
j = next[j]
if j == len(p):
return i - j
else:
return -1
def get_next(p=str()):
next = [0] * len(p)
next[0] = -1
i, j = 0, -1
while i < len(p) - 1:
if j == -1 or (p[i] == p[j]):
i, j = i + 1, j + 1
if p[i] != p[j]:
next[i] = j
else:
next[i] = next[j]
else:
j = next[j]
return next
if __name__ == '__main__':
s = 'abcdabcefgsabc'
# print get_next(s)
print kmp_search(s, "abcefg")
求next数组
next数组的意思就是 next[i] = len; 长度为i的数组的前缀和后缀相等的最大长度。 例如abcdabc就是 next[7] = 3; 相等的前缀和后缀最长是abc长度为3。
因此这里是先i++,j++，再赋值next，因为kmp用next地时候是if s[i] != p[j], j = next[j].
def getNext(self, s):
next = [-1 for _ in range(len(s))]
i, j = 0, -1
while i < len(s) - 1:
if j == -1 or s[i] == s[j]:
i, j = i + 1, j + 1
next[i] = j
else:
j = next[j]
return next
扩展kmp
拓展kmp是对KMP算法的扩展，它解决如下问题：
- 问s串与t串的每一个后缀的最长公共前缀
强化条件：当s与t完全相同时
先尝试通过强化条件，降低一下难度：假如s与t完全相同，扩展kmp该如何实现？
当s与t完全相同，其实问题可以进一步转化为“s与s的每一个后缀的最长公共前缀”。
参考： https://oi-wiki.org/string/z-func/
# Python Version
def z_function(s):
n = len(s)
z = [0] * n
l, r = 0, 0
for i in range(1, n):
if i <= r and z[i - l] < r - i + 1:
z[i] = z[i - l]
else:
z[i] = max(0, r - i + 1)
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l = i
r = i + z[i] - 1
return z