kmp|kmp 算法 kmp算法

前言: 少 kmp 多学习

0X00 算法板子 831. KMP字符串
【kmp|kmp 算法】感觉还是很难理解

n, s1 = int(input()), input() m, s2 = int(input()), input()ne = [0] * (n+1)# 求出 ne 数组 # 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=" ")