KMP字符串匹配算法.pdf

文档介绍：IT-Homer 专栏
成功是优点的发挥,失败是缺点的积累! 不为失败找理由,只为成功找
方法……
KMP字符串匹配算法
分类: Algorithm 2011-12-28 16:56 496人阅读评论(0) 收藏举报
KMP算法,Knuth-Morris-Pratt Algorithm,一种由Knuth()、Morris()和
Pratt()三人提出的一种快速模式匹配算法。
KMP朴素算法
原理:子串pattern依次与目标串target中的字符比较,如果相等,继续比较下一个字符;如果
不等,pattern右移一位,重新开始比较,直至匹配正确或超出target。
示例:子串pattern={aabaa},目标串target={aababaacaabaa},比较过程如下图:
特点:思路简单、代码直观;但效率低、有回溯、不够简洁、时间复杂度高
// 在target中查找子串pattern的起始位置,pos初始为0
int index(char *target, char *pattern, int pos)
{
if(NULL == target || NULL == pattern){
return -1;
}
int k = pos, j = 0;
while(k<strlen(target) && j<strlen(pattern)){ // 未超出字符串长度
if(target[k] == pattern[j]){ // 字符相同,则继续向后比较
k++;
j++;
}else{ // 如果不同,则回溯重新查找
k = k - j + 1;
j = 0;
}
}
if(j == strlen(pattern)){ // 如果找到,则返回字串起始位置(首次匹配)
return k - strlen(pattern);
}else{ // 如果没找到,则返回-1
return -1;
}
}
小结:在最坏的情况下,每次比较都在最后一个字符出现不等(如aaaaaaaaaaaaab和ab)
假设pattern长度为m,target长度为n,则每趟最多比较m次,最多循环比较(n-m)趟,总比较次数为m*(n-
m),即时间复杂度为O(m*n)
KMP算法的演变
1
我们由上面KMP朴素算法的例子来引出一个问题。
为了便于问题分析,令P(pattern),T(target),字符数组下标从0开始。通过仔细分析,发现
P(Pattern)前4个字符是匹配的,只有最后一个字符P[4]不匹配!
如果P右移1位,P前两字符aa又将与T(target)的ab不匹配
如果P右移2位,P第一个字符a就与T的b不匹配
如果P右移3位,P前两字符aa又将于T的ab不匹配(同右移1位的情况)
如果P右移4位,P第一个字符a就与T的b不匹配(同右移2位的情况)
如果P右移5位,即P跨过已经与T比较过的五位了,省去了右移1、2、3、4位的步骤
为什么是5位呢?我们再深入分析,转换思考问题的侧重点,发现5位字符正好是P(Pattern)子串的长度,是
不是P子串本身就