KMP字符串匹配算法

向右看齐 2024-04-18 14:10 83阅读 0赞

1：原始暴力算法

每次移动一下，然后重新从头开始对应

缺陷： 比较次数过多

示例    1：a,a,a,a,a,a,a,b

2：a,a,a,a,b

2：kmp算法

找前缀表：及计算前缀和后缀最大相同数。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70][]

然后对比：从失败处，根据前缀3，找到了第4个a处，使得p\[3\]与失败处对应,然后用p\[3\]与此处的值做对比。（与暴力算法比，虽然都只移动了1位，但对比的开始下标不同）。（非常巧妙，大家可以思考下）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70 1][]

从匹配失误的下表开始匹配

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6648f7f6fe2040fcb2102f8f939a2427.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9fa60838fe3d4ede8c0643150df39fce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4NjU2NzA3_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/755e1af47fdc40e38fab57fd380f3f90.png

发表评论取消回复

表情：

评论列表（有 0 条评论，83人围观）

还没有评论，来说两句吧...

相关阅读

相关 KMP字符串匹配算法

：原始暴力算法每次移动一下，然后重新从头开始对应缺陷：比较次数过多示例 1：a,a,a,a,a...

向右看齐/ 2024年04月18日 14:10/ 0 赞/ 84 阅读

相关算法 - KMP算法(字符串匹配)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

本是古典何须时尚/ 2023年07月03日 10:47/ 0 赞/ 14 阅读

相关 KMP算法（字符串匹配）

kmp算法字符串匹配 import java.util.Scanner; //1. 判断数组 C D 中是否分别对应包含数组A B，返回匹配的第一个数

小灰灰/ 2022年12月08日 05:34/ 0 赞/ 250 阅读

相关字符串匹配算法(KMP)

1、BF算法 BF算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等

我不是女神ヾ/ 2022年08月27日 08:57/ 0 赞/ 257 阅读

相关字符串匹配KMP算法

本部分内容转载在：http://www.cnblogs.com/c-cloud/p/3224788.html 前言　　　　之前对kmp算法虽然了解它的原理，即求出P0··

一时失言乱红尘/ 2022年08月21日 10:47/ 0 赞/ 301 阅读

相关字符串匹配——KMP算法

字符串匹配——KMP算法 KMP(Knuth-Morris-Pratt)算法分两部分，先计算Next\[\]数组，然后进行串匹配。 KmpNext算法描述如下：

雨点打透心脏的1/2处/ 2022年06月16日 12:52/ 0 赞/ 355 阅读

相关算法—KMP字符串匹配

算法—KMP字符串匹配现在有一个问题，要从一个字符串中查找出指定子串的位置(初始下标)，通常地，我们会使用朴素的字符串匹配算法，如下面这道题给出主串和需要查找

短命女/ 2022年05月16日 01:39/ 0 赞/ 530 阅读

相关 KMP字符串匹配算法

写在前面 KMP算法典型例题输入第一行一个整数N，表示测试数据组数。接下来的N\2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，

约定不等于承诺〃/ 2022年05月10日 02:10/ 0 赞/ 351 阅读

相关字符串匹配算法kmp

问题:给定原串origin,求target 串在原串第一次出现的位置,若不存在,输出-1 例如: origin:abcdef target:bc 输出:1 朴素

不念不忘少年蓝@/ 2022年03月22日 07:22/ 0 赞/ 330 阅读

相关字符串匹配算法KMP

KMP算法的原理，这里我不写，建议参考： [http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80

╰+攻爆jí腚メ/ 2022年01月14日 00:41/ 0 赞/ 401 阅读