前言: 少 kmp 多學(xué)習(xí)
0X00 算法板子
感覺還是很難理解
n, s1 = int(input()), input()
m, s2 = int(input()), input()
ne = [0] * (n+1)
# 求出 ne 數(shù)組
# ne[i] 表示前后綴中最長的公共串的長度
# 且 ne[i] 又是前綴的后面一位的索引
# j 表示上一次的前綴的后面一位的索引
j = 0
for i in range(2, n+1):
while j != 0 and s1[i-1] != s1[j]: j = ne[j]
if s1[i-1] == s1[j]: j += 1
ne[i] = j
# 開始匹配
j = 0
for i in range(m):
while j != 0 and s2[i] != s1[j]: j = ne[j]
if s2[i] == s1[j]: j += 1
if j == n:
j = ne[j]
print(i-n+1, end=" ")
