有人能为我建议一个最坏情况的“文本串 - 模式串”来测试KMP算法实现吗？
KMP字符串查找算法的最坏情况是什么？
7
- Mustafa Zengin
2
KMP具有线性运行时复杂度，因此任何以目标字符串结尾的字符串都将在最坏情况下运行。如果您的实现是多查找，则每种情况都以线性时间运行。 - davin
1我会在这里写下我的答案，因为问题已经关闭了：在Knuth、Morris和Pratt的论文《字符串快速模式匹配》中，他们证明了该算法的最坏情况是定义为斐波那契字符串的字符串，其定义如下：
$ \phi_1 = b, \phi_2 = b, \phi_n= \phi_{n-1}\phi_{n-2} $ 请查看论文的第5节理论考虑部分。 - Marin Shalamanov
2个回答
7
我会说，像这样的一个模式
xx........x
| n times |
并且一个类似于字符串的东西
xxx.........xyx...........xy....
| n-1 times | | n-1 times |
这可能是最糟糕的情况之一，但它仍然是O(m+n)
- Luchian Grigore
2
1每当出现不匹配时，我们根据前缀后缀匹配表将模式字符指针向左移动。例如，在您的答案中，每次遇到y字符时，我们都会发现不匹配，并且我们会将模式的字符指针每次向左移动1个字符。如果文本中有c1个x字符和c2个y字符，则我们得到的总比较次数为（c1 + c2 *模式大小）。我是对的吗？ - Farsan Rashid
1@FarsanRashid 我一直在练习算法/数据结构，并搜索了KMP算法的最坏情况。在阅读了这个答案之后，我也想到了你上面写的同样的事情...真是巧啊，我认识这个人xD - Kaidul
2
你可以在这里找到关于KMP算法的任何信息：
KMP算法
摘要如下：
Knuth、Morris和Pratt通过对朴素算法进行紧密分析，首次发现了线性时间字符串匹配算法。Knuth-Morris-Pratt算法在扫描文本时保留了朴素方法浪费的信息。通过避免这种信息浪费，它实现了O(n + m)的运行时间，在最坏情况下是最优的。也就是说，在最坏情况下，Knuth-Morris-Pratt算法必须至少检查一次文本和模式中的所有字符。
你应该能够澄清你对该算法的理解，并在那里找到需要的内容。
希望这有所帮助。
Knuth、Morris和Pratt通过对朴素算法进行紧密分析，首次发现了线性时间字符串匹配算法。Knuth-Morris-Pratt算法在扫描文本时保留了朴素方法浪费的信息。通过避免这种信息浪费，它实现了O(n + m)的运行时间，在最坏情况下是最优的。也就是说，在最坏情况下，Knuth-Morris-Pratt算法必须至少检查一次文本和模式中的所有字符。
你应该能够澄清你对该算法的理解，并在那里找到需要的内容。
希望这有所帮助。
- Ricky Bobby
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接