哭了~正在学数据结构中的 KMP 算法

来源：百度知道 编辑：UC知道 时间：2024/07/03 04:49:28
我哭了，下学期开数据结构这门课，现在假期闲着无聊，提前看了看严蔚敏写的数据结构C语言版，前面看的都觉得简单，昨天看到串模式匹配的 KMP 算法了，到现在还没看明白，哭了，谁能给我点详细、深入、深入的不能再深入、详细的不能再详细的介绍 KMP 算法的资料（或网址），找不着我就哭了，伤自尊了。
madmanahong 你回答的太好了，你懒得回忆了，所以我懒得选答案了...

http://wenku.baidu.com/view/eb000a1bff00bed5b9f31dd9.html###

这个比较详细，反正这么难的算法，一般面试不会考吧。

百度百科可否？

http://baike.baidu.com/view/574553.html?wtp=tt

你得先理解有穷自动机，

KMP是为了解决有穷自动机的一些效率问题出现的，具体啥懒得回忆了。

KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”
解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。
之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。这时，或许你突然明白了AVL 树为什么叫AVL，或者Bellman-Ford为什么中间是