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 为模式串中匹配的起点
目录
相关文章
|
3月前
|
算法 测试技术 C#
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
|
3月前
|
算法 C++ 索引
leetcode-28:实现 strStr()(字符串匹配,暴力匹配算法和KMP算法)
leetcode-28:实现 strStr()(字符串匹配,暴力匹配算法和KMP算法)
32 0
|
2月前
|
机器学习/深度学习 算法 C语言
【编码狂想】深度探索C++编程之旅:“数组、字符串、函数与KMP算法解密“
【编码狂想】深度探索C++编程之旅:“数组、字符串、函数与KMP算法解密“
73 0
|
13天前
|
存储 算法
图解Kmp算法——配图详解(超级详细)
图解Kmp算法——配图详解(超级详细)
|
18天前
|
算法 测试技术 C#
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
|
18天前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)
|
1月前
|
算法
白话 KMP 算法
白话 KMP 算法
14 2
|
1月前
|
算法 Java 索引
算法基础:KMP算法详细详解
算法基础:KMP算法详细详解
|
2月前
|
算法 测试技术 C++
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
|
2月前
|
算法 搜索推荐 程序员
C语言第三十三练—— KMP算法和扩展 KMP算法
C语言第三十三练—— KMP算法和扩展 KMP算法
34 0