KMP
字符串匹配问题的朴素解法是两个指针i j
,分别扫描字符串s
和模式串p
,如果s
以下标为i
的子串与p
完全一样则返回i
否则i++, j = 0
(子串开头指针后移,模式串指针归零)反复执行一直到扫描完所有子串。
KMP对过程的优化主要体现在模式串每次移动的距离,如果我们能判断下一次模式串的头部应该停在什么地方,而不是每次都向右一格,向右一格......就能降低时间复杂度。根据分析我们得知移动的距离只与模式串本身有关,所以可以使用预处理输入的思想,即构造next
数组
谈谈自己对i
和j
意义的理解:在模式串需要移动的时候,i
指向的是本次匹配中s
第一个不匹配的元素的下标,而j
指向的是模式串中本次匹配中最后一个匹配的元素在p
中的下标,两者是一前一后的,所以我们在循环匹配的过程中比较的一直都是a[i]
和p[j+1]
,所以在模式串移动( j = ne[j]
)之后指向的正好是本次模式串正确匹配的最后一位,此时的j+1
和a[i]
又能构成正确的比较关系。
while j and ...
的目的是防止初始时a[i] == p[j+1] => a[0] == p[1]
是恒成立的
构造next
和使用next
的板子是几乎一样的
m = int(input())
ne = [0]*(m+1)
p = list(input())
p.insert(0, '\0')
n = int(input())
a = list(input())
a.insert(0, '\0')
i, j = 2, 0
while i <= m:
while j and p[i] != p[j+1]:
j = ne[j]
if p[i] == p[j+1]:
j += 1
ne[i] = j
i += 1
i, j = 1, 0
while i <= n:
while j and a[i] != p[j+1]:
j = ne[j]
if a[i] == p[j+1]:
j += 1
if j == m:
print(i-j, end=" ")
j = ne[j]
i += 1