Posted on 2006-10-10 21:29
oyjpart 阅读(7450)
评论(3) 编辑 收藏 引用
KMP算法是由
Knuth, Morris, Pratt三位牛人提出的快速匹配算法 得到了非常的广泛的应用
鉴于最近教材正在学KMP算法 我在此对次算法进行一下简略分析 不清楚的同学可以参考一下
//By Optimistic
说明：字符串查找中，被查找的叫做目标串，查找的叫模式串。如：
目标串：T[] = 01001010100001 模式串 P[] = 1010
算法来源: 朴素的匹配效率太低。考虑改进：1.当模式串与目标串在i位置比较不同时，下一个应该从目标串的哪里开始比较？2。下一个应该从模式串的哪个开始比较？
于是经过一些简单的逻辑推理 我们得到了KMP算法的思想 让目标串没有回溯 并且模式串尽可能向后滑动
我们用next[i]这个数组来存储当模式串的第i位比较出现不匹配时 模式串的从哪里开始比较
比如next[i] = 2 相当于从从P[2]开始比较 如果next[i] = -1 代表模式串的第一个与目标串的下一个比较
KMP的算法的精华就在于对next[i]的求取，采用next[i-1]=>next[i]的方法求得next[i]的值
下面我们来看看next[i]的求取
string str;
cin >> str;
int * next = new int[str.length()+1];
int i = 0, j = -1;
next[0] = -1;
while(i < str.length())
{
while(j>=0 && str[i]!=str[j])
j = next[j];
i++;
j++;
if(str[i] == str[j]) //修正
next[i] = next[j];
else next[i] = j;
}
其中具体的细节其参考 我同寝室同学写的KMP算法详解：
http://www.cppblog.com/warrior0032/archive/2006/10/10/13543.html其中解释了算法的基本思想和实现过程
我对此算法作几个分析：
1。为什么要修正next[i]值？为什么只要修正一次？当我们分析到模式串中的第i位于目标串不同时 求得应该从K位开始比较 但是如果第K位于第I位相同的时候 第K位一定与目标串也不同因此应该再次改成当K位比较不同时的NEXT值 即 NEXT[K]
由于NEXT是由左向右推出来的 所以只需修正一次 (数学归纳法？呵呵。。。）
2。程序没有使用一个数组来保存未修正时的NEXT值 而直接用J来充当这个功能 但是J是由NEXT（已修正）得来的 那么有没有可能J得不到正确的值？这个问题最先是我自己想的 后来验证了一下 J一定能够得到正确的值
下面我们来分析一下
下标 0 1 2 3 4 5 6 7 8 9 10 11 1213
目标串 0 1 0 0 1 0 1 0 1 0 0 0 0 1
j(未修正的next) -1 0 0 1 1 2 3 2 3 2 3 4 1 1
修正了的next -1 0 -1 1 0 -1 3 -1 3 -1 0 4 1 0让我们看看但模式串比较到了12位的时候（下标为11）
next[11] = 4; next[4] = 0; j|4 = 1...
这时候next[4]拿到的并不是正确的J值！！！
这会导致什么？会导致略过一个比较 即p[11]与p[1]的比较被略过！直接比较了p[11]与p[0]！
是否可以略过这个比较？！
答案是肯定的.
根据逻辑推理 如果p[11]与p[4]不等 而p[4] = p[1]那么p[11]与p[1]一定不等 所以可以略过
这样说似乎很牵强 我们再回想一下NEXT数组的意义 即当我们比较到i位时不等 应该由哪一位重新开始比较 而实际上 这个过程相当于在 7-11的这个串中查找0-3！所以根据NEXT数组的意义 我们也可以知道 这里并不会导致错误 由于被略去的比较一定不需比较 因此 J始终可以得到正确的未修正的NEXT值！
3。
KMP算法的局限性 由于KMP算法完全由模式串来考虑滑动 可能忽略一些很好的滑动机会
如当目标串某位不同于模式串时 若此目标串中的字符从未在模式串中出现 那么就可以直接滑过去所有的 这时候 目标串也起了 确定滑动距离 的作用．这其实就是ＢＭ算法．有兴趣的同学可以参考下列连接
http://www.cnpaf.net/Forum/htm_data/5/0507/1832.html1977年,Robert Boyer和L.Moore发表了一种新的精确字符串匹配算法,这种算法在逻辑上相对于现有的算法有了很大的超越.它对要搜索的字符串实施逆序字符比较,而且有一种找到了不匹配就不需要对整个字符串进行搜索的方法.这种算法还有最初在PDP-10汇编器上实现的奇迹.
好了 到这里了吧 呵呵 我休息下 最近晕糊涂了