KMP 算法小结

简介: KMP 算法小结

算法包括5个重要元素:

主串S,假定为字符数组
模式串P,假定为字符数组
int next[]
主串索引 i ,从0开始
模式串索引 j ,从0开始

next[j] :P[0]~P[j-1] 组成的字符串,首尾依次匹配,得到的相同元素的个数,规定next[0] = -1

要点:

1.主串索引 i 在匹配过程中只增加,增加原因有两个:

与模式串对应位匹配OK,和 j 同时增加;
匹配不OK,且 next[j] 的值为 0 或 -1时,和 j同时增加; 

2.模式串索引 j 在匹配过程中则有增减

匹配成功时和 i 同时增加;
减少是因为匹配失败,获取 j = next[j] 时变小;

3. j 为模式串中匹配的起点
目录
相关文章
|
7月前
|
算法
数据结构中的KMP算法及其改进算法
KMP算法通过引入部分匹配表,有效避免了重复计算,从而将字符串匹配的时间复杂度降低到O(m+n)。通过进一步优化next数组,KMP算法的效率得到了进一步提升。对于大规模字符串匹配问题,KMP算法及其改进算法提供了高效的解决方案,是计算机科学领域的经典算法之一。
109 3
|
3月前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
25 0
|
3月前
|
算法
KMP算法
KMP算法
44 0
|
5月前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
6月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
144 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
5月前
|
算法
KMP算法
KMP算法
39 0
|
6月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
|
7月前
|
人工智能 算法 BI
一篇文章讲明白KMP算法(俗称看毛片算法)
一篇文章讲明白KMP算法(俗称看毛片算法)
70 0
|
7月前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法
|
8月前
|
算法 搜索推荐 程序员
第六十三练 字符串匹配 - KMP算法
第六十三练 字符串匹配 - KMP算法
52 2

热门文章

最新文章