KMP算法简单解析(未优化，旨在揭示原理)
-
void MakeNext(char *p ,int *next)
-
{
-
int len ,i ,k;
-
len = strlen(p);
-
-
for(i = 1 ,k = 0;i < len ;i++){
-
while(k > 0 && (p[i] != p[k]))
-
k = next[k-1];
-
if(p[i] == p[k]){
-
k++;
-
next[i] = k;
-
}
-
}
-
}
-
void KMP(char *p ,char *t ,int *next)
-
{
-
int src,dst;
-
int i = 0,k;
-
-
src = strlen(p);
-
dst = strlen(t);
-
while(i < src){
-
printf("%c:%d\n" ,p[i] ,next[i]);
-
i++;
-
}
-
-
for(i = 0 ,k = 0; i < dst ;++i){
-
while(k > 0 && t[i] != p[k]){
-
k = next[k-1];
-
}
-
if(t[i] == p[k]){
-
k++;
-
}
-
if(k == src){
-
printf("find dst.[%d][%d]-i[%d][%s]\n" ,k , src, i-k+1,&t[i-k+1]);
-
}
-
}
-
}
KMP算法的思想就是为了避免回溯查找，被匹配的字符串一直向前不后退，模式字符串来回匹配。
模式字符串需要进行统计，当被匹配的字符匹配失败的时候，需要模式字符串从第几个字符来进行匹配。
之所以不需要被匹配的字符串进行回溯查找，是利用了模式字符串已经匹配成功的记录。
模式字符串统计的是每个字符与自己之前的第几个字符能匹配。
这个统计结果放到所谓的next数组里面，也叫前缀数组。
举个例子:
0123456789
abcabcabcd
0001234560
如上模式字符串，前三个字符“abc” 没有相同的、所以他们对应的next数组里，
next[0]=0,next[1]=0,next[2]=0
当到第四个字符'a'的时候，因为之前的三个字符都没有统计到出现重复项，所以第四个字符'a'需要从第一个字符开始匹配。
第一个字符为'a'与第四个字符相等，则表明当模式字符串与被匹配的字符串在匹配模式字符串第五个字符'b'匹配失败的时候，因为
第四个字符'a'匹配成功了，所以在模式字符串移动的时候，取第四个字符'a'对应的next值进行匹配。
第四个字符'a' 对应的next[3]=1。这块需要说为什么第四个字符'a'对应第一个字符'a'的数组下标为0，而next[3]却要++。
这样是为了在以后模式字符串统计出现不匹配的字符时，去匹配之后一个字符。
比如abcabd
d之前的几个字符对应的next值为
0123456789*！
abcdabcdabde
abcdabcdabda
000012345601
当d做匹配的时候，d与c也就是第三个字符做比较。d!=c 则查看Buf[next[index(c)-1]]的字符与d做比较。、
这个比较的意思是，d之前的字符b已经有匹配的字符了，然后d与b之前的匹配到的字符的后面一个字符去做比较。这样做了是按照
abda这个顺序去匹配的，为了保持一致。
之前的第五、第六字符'b','c'与第二、第三字符处理与第四个字符相同
next[4]=2、next[5]=3
第七个字符'a'，又是a此时与第四个字符'a'进行匹配 next[6]=4
第八、第九字符'b','c'与之相同 next[7]=5,next[8]=6
第十个字符'd' 与第七个字符比较'a'不相等，则取第()7-1)字符对应的next值比较，表示第七个字符与之前的第next[6]个字符匹配，
next[6]=4，也就是第七个字符与第四个字符比较'd'与'a'不相等，重复上步操作、与第三个元素对应的next值相比，即与第next[3]=0比较
'd'与'a'比较，此时next已经查找到第一个元素表示都没有匹配到，说明d与之前的所有元素都不匹配，则next[9]=0
此时next数组初始化完成
然后开始与被匹配的字符串进行匹配。
首先从第一个字符互相匹配，如果匹配成功了开始匹配下一个字符。
当匹配失败的时候，模式字符串首先查找匹配失败的字符的前一个字符，因为前一个字符匹配成功了。获取到前一个字符对应的next值，模式字符串则总next值对应的
字符开始与当前的被匹配的字符串进行匹配。直到将模式字符串完全匹配完毕。
总结:
最后再简单的总结下，KMP算法就是为了保证被匹配的字符串不会回溯查找，并且模式字符串按照顺序去匹配。
阅读(2506) | 评论(0) | 转发(0) |
