已知字符串S 为“abaabaabacacaabaabcc”，模式串 t 为“abaabc”。采用 KMP 算法进行匹配，第一 次出现“失配”(s[i]≠t[j]) 时，i=j=5，则下次开始匹配时，i 和 j 的值分别是 （） 。
暴力匹配与kpm模式匹配
发表于 2019-02-19 22:46:52
回复(0)
更多回答
如果以上回答看不明白的朋友，或者KMP算法不明白的朋友可以参考一下这篇博客。http://blog.csdn.net/yutianzuijin/article/details/11954939/
发表于 2017-09-03 17:58:49
回复(0)
我贴一个阮一峰大佬7年前的文章吧，将KMP算法讲的很清楚http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
发表于 2020-06-10 22:10:50
回复(0)
发表于 2019-08-16 12:41:31
回复(2)
由题中“失配 s[i] ≠ t[j] 时， i=j=5 ” ，可知题中的主串和模式串的位序都是从 0 开始的（要注意灵活应变）。 按照 next 数组生成算法，对于 t 有：
编号 | 0 | 1 | 2 | 3 | 4 | 5 |
t | a | b | a | a | b | c |
next | - 1 | 0 | 0 | 1 | 1 | 2 |
依据 KMP 算法“当失配时， i 不变， j 回退到 next[j] 的位置并重新比较”，当失配 s[i] ≠ t[j] 时，i=j=5 ，由上表不难得出 next[j]=next[5]=2 （位序从 0 开始）。从而最后结果应为： i=5 （ i 保持不变）， j=2 。
发表于 2016-12-13 18:14:24
回复(0)
笔记：感谢牛友指引，终于清楚KMP算法了
解析：根据上面视频学习next数组和KMP算法序列的比较和移动可知：next数组为：
比较字符串和模式串：
编辑于 2021-03-31 14:08:42
回复(0)
分析：但凡有一点点对KMP思想的理解，就很容易排除A,D。因为文本串S在失配时指针不动。
剩下BC,而B显然是不对的，因为，我们目的是在失配时让模式串中指针往右游走更多距离。因为比较时已经看到了挺多字符，不用起来做一个快速的决策，实在过于浪费。
因此，单纯解此题而言，不用真正用KMP去求解，用基本思想就足够了。
而如果是动手解，需要注意下标是从0开始的。即abaabc比较到c失配了，该在模式串中选择的是第三个字符(P[2])与文本串比较。此时i = 5,S[5] = a.恰好相等。我们再往前看S[5]之前的是ab, P[2]之前的也是ab,即前面都是匹配的。从这里出发再往后进行比较即可。
所以i = 5(没变)，j=2(指示下一个模式串的下标),此时S[i] = P[j]。这正是失配时问题的解决方案。
发表于 2017-08-15 16:08:30
回复(0)
根据KMP算法中的next数组定义 next[j] = 3 就说明 需要 然模式串从 0 开始 移动三位 即 移动到 j = 2
发表于 2023-09-07 14:02:29
回复(0)
问题信息
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
由题中“失配 s[i] ≠ t[j] 时， i=j=5 ” ，可知题中的主串和模式串的位序都是从 0 开始的（要注意灵活应变）。 按照 next 数组生成算法，对于 t 有：
编号
0
1
2
3
4
5
t
a
b
a
a
b
c
next
- 1
0
0
1
1
2
依据 KMP 算法“当失配时， i 不变， j 回退到 next[j] 的位置并重新比较”，当失配 s[i] ≠ t[j] 时， i=j=5 ，由上表不难得出 next[j]=next[5]=2 （位序从 0 开始）。从而最后结果应为： i=5 （ i 保持不变）， j=2 。