KMP
作者:
成理第一深情
,
2024-01-22 09:49:08
,
所有人可见
,
阅读 47
Acwing 831.KMP字符串
题解
- 核心是最长前后缀
- next数组的含义是如果下一个字符不匹配,最长可以跳过的字符数是多少
p = [0] * 100010 # 模式串p
s = [0] * 1000010 # 主串s
ne = [0] * 100010 # next数组
if __name__ == "__main__":
n = int(input())
p[1:n+1] = list(input())
m = int(input())
s[1:m+1] = list(input())
# print(p, s)
# 求ne数组的过程
# ne[1]=0, 故i从2开始
# j其实是记录的跳过多少个字符
j = 0
for i in range(2, n + 1):
while j and(p[i] != p[j + 1]):
j = ne[j]
if p[i] == p[j + 1]:
j += 1
ne[i] = j
# KMP匹配过程
# 主串上的指针i从前往后遍历且不会回退
j = 0
for i in range(1, m + 1):
# 两个条件
# 1.next[j]!=0
# 2.下一个字符不能匹配成功就j=next[j]
while j and (p[j + 1] != s[i]):
j = ne[j]
if s[i] == p[j + 1]:
j += 1
if j == n:
# 匹配成功
print(i - n, end=' ')
j = ne[j]