前言: 少 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=" ")
KMP 学习记录 kuangbin专题十六——KMP KMP 学习总结 朴素 KMP 算法 拓展 KMP 算法（E...
最近学到KMP算法，下面讲讲对KMP算法的一些个人理解，希望对大家有帮助！ 对于KMP算法的理解： 整个KMP算法...
字符串的查找：朴素查找算法和KMP算法 暴力匹配算法与KMP算法（串的匹配） 字符串查找算法BF和KMP 字符串匹...
KMP算法 算法匹配
问题 目录KMP是什么，做什么用的KMP算法的高效体现在哪如何KMP算法的next数组KMP的代码KMP的时间复杂...
KMP算法——寻找子串位置 1、KMP算法简介： KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J....
前面我们介绍非常高效的 BM 算法，今天我们介绍另一个非常出名且高效的 KMP 算法。 KMP 算法思想 KMP ...
转载请注明出处: KMP算法及优化 今天看到同学在复习数据结构书上的KMP算法，忽然发觉自己又把KMP算法忘掉了，...
一、是什么？ 注意，是KMP算法，不是MMP哈，我没有骂人。KMP算法是用来做字符串匹配的，除了KMP算法分，还有...
KMP算法
本文标题：kmp 算法
本文链接：https://www.haomeiwen.com/subject/tqyduhtx.html
网友评论