请选择 进入手机版 | 继续访问电脑版

KMP算法的实现(超详解)

[复制链接]
会眨眼睛的鱼儿 发表于 2021-4-21 07:26:59 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
KMP算法的实现

要求解KMP算法,首先要得到next数组,也有的地方叫prefix数组。
先用手算的方法求得
假设模式串为abacab;
第一步列出模式串的所有前缀(包罗自身):
(1)a
(2)ab
(3)aba
(4)abac
(5)abaca
(6)abacab
第二步将各个前缀看作一个独立的字符串,依次求得各个字符串的最长前后缀的长度,这里的前后缀是不包罗自身的(前缀不包罗最后一个字符,后缀不包罗第一个字符):
详细来看第一个字符串只有一个字符,因此它的前缀后缀都为空,所以它的最长公共前后缀的长度为0;
第二个字符串它的最长前缀为a,最长后缀为b,无公共部分,所以最长公共前后缀的长度为0;
第三个字符串最长前缀为ab,最长后缀为ba,不相等,淘汰前后缀的长度,前缀只剩下a,后缀也为a,因此长度为1;
第四个字符串它的最长前缀为aba,最长后缀为bac,前后缀不相等,淘汰前后缀的长度,前缀变为ab,后缀变为ac。前后缀不相等,继续淘汰前后缀的长度,前缀为a,后缀为c,不相等,所以长度为0;
五六同理,五的最长公共前后缀为a,长度为1;六的最长公共前后缀为ab,长度为2;
(1)a 0
(2)ab 0
(3)aba 1
(4)abac 0
(5)abaca 1
(6)abacab 2
求得的长度就是prefix数组的各个元素的值;

也可以直接将prefix数组的值全部右移一位,然后将prefix[0]的值设为-1;
下面思量如何用代码来实现;
先观察第五个字符串的最长前后缀长度为1,第六个字符串的最长前后缀长度为2;第六个字符串比第五个字符串多了一个字符b,而第五个字符串的的第二个字符刚好为b。所以后一个字符串的长度和前一个字符串是有关系的,当前一个字符串的最长公共字符串的长度+1的谁人字符和此时的字符串最后一个字符相等时,那么当前字符串的长度应该是前一个字符串的最长公共前后缀的长度+1。
界说两个变量i和len;
i指向当前字符串的最后一个位置;
len指向前一个字符串的最长公共字符串的长度+1的位置,因为数组的下标是从0开始的;所以len的值应该为前一个字符串的prefix的值+1-1,即前一个字符串的prefix的值;
初始化prefix[0]=0(任何情况下都为0,因为只有一个字符时无前缀和后缀);
i=1(指向第二个字符串的最后一个位置);
len=0;
如果p==p[len],那么len++;prefix=len;(当前字符串的长度比前一个字符串的长度多1);
如果p!=p[len]时,这也是最难明白的地方,

如图所示,此时p[len]!=p,图中的1、2部分为前面字符串的最长公共前后缀。要使当前字符串有公共前后缀,那么图中的圆圈所示部分应该相等,

又因为第1,2部分的字符串是相等的,所以第一部分的两个圆圈的内容是相等的,且第一个圆圈的最后一个字符为i所指的字符。

所以当p[len]!=p时,len=prefix[len-1](len指向前一个字符的最长公共前后缀的下一个位置如图一所示,prefix[[len-1]指向第一部分的最长公共前后缀的下一个位置,也就是第一部分第一个圆圈的最后一个位置)接下来的p==p[len]的判定会判定第一部分第一个圆圈的最后一个位置和当前i所指的位置的值是否相等,如果相等,那么prefix的值应该为第一部分的最长公共前后缀的值+1,第一部分的最长公共前后缀的长度为prefix[i-1]的值也就是当前len的值。即len++;prefix=len;如果判定p==p[len]的效果为false,那么继续在第一部分的第一个圆圈内递归查找,比力第一个圆圈内的最长公共前后缀加一的位置和i所指的位置是否相等。说了这么多,应该不难明白了吧。下面看看代码。
  1. void prefix_table(char p[],int prefix[],int n){        prefix[0]=0;        int len=0;        int i=1;        while(i0){/*当len=0时,len-1的值为-1,数组下标越界*/                                 len=prefix[len-1];                        }else{                                prefix[i]=0;/*当递归查找到第一个字符时,若果还不相等,那么这个字符串的最长公共前后缀的长度肯定为0*/                                 i++;                        }                }        }}
复制代码
将prefix数组右移一位(kmp算法指针回溯的位置为前一个字符串的最长公共前后缀的长度所指的位置)
  1. void move_prefix_table(int prefix[],int n){        int i;        for(i=n-1;i>0;i--){                prefix[i]=prefix[i-1];        }        prefix[0]=-1;}
复制代码
查找字符串
[code]void search(char text[],char p[]){        int n=strlen(p);        int *prefix=(int *)malloc(sizeof(int)*n);        prefix_table(p,prefix,n);        move_prefix_table(prefix,n);        int m=strlen(text);        int i,j;        while(i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )