KMP算法中的nextval函数值的原理,求详细推导
答案:1 悬赏:80
解决时间 2021-03-28 15:28
- 提问者网友:我一贱你就笑
- 2021-03-28 07:56
KMP算法中的nextval函数值的原理,求详细推导
最佳答案
- 二级知识专家网友:詩光轨車
- 2021-03-28 08:31
1get_nextval(int *nextval,const char *string)
2{
3 int num=strlen(string);
4 int i=0,j=-1;
5 nextval[0]=-1;
6 while(i 7 {
8 if(j==-1||string[i]=string[j])
9 {
10i++;
11j++;
12if(string[i]==string[j])
13 {
14 nextval[i]=nextval[j];
15 }
16 else
17 {
18nextval[i]=j;
19 }
20 }
21 else
22 {
23 j=next[j];
24 }
25 }
kmp的思想主要是通过nextval数组来指示“假如在子串与主串匹配过程中在某一位(假设为 j )匹配失败(不相等)时,子串应回到的位置。”以此区别于朴素模式匹配的一旦在某位匹配失败,就从头比较的特点。所以在生成与子串等长的nextval数组时,nextval数组每一个元素标识的就应该是当在子串的第j位与主串匹配失败时,应回到子串的哪一位。
设子串string为"abqabc"。主串为"abqabqabc";生成nextval的思想是:假设目前 j 和 i 各处string的某一个位置,对比string[j]和string[i](代码第8行),若相等,j 和 i 都向前一步,j , i 向前一步(代码10~11行)是为了下一次匹配,同时是为了在nextval[i]记录当子串与主串匹配失败时应回到子串的哪一位继续比较下去(代码第14或18行)。比如说当子串与主串在第六位(子串的c跟主串的q)匹配失败时,我们会希望nextval[5]记录的是2,这样"ab"就不需重新匹配。
可以看到在子串的 c 之前,"abqab" 是前缀(ab)与后缀(ab)相等的,有两位,所以在nextval[5]记录 2 ,意思就是当 c 与主串匹配失败时,直接回到子串string[2]继续比较即可。
在制作nextval数组的过程中,i只会往前,j如果遇到前缀string[j]不等于后缀string[i]时会回溯,往回找,看能不能找到与后缀相等的前缀。比如子串为"abqabac",制作nextval数组时比较到第三位(q)跟第六位(a)时,此时q不等于a,所以j往回找,拿第二位(b)跟第六位(a)比较,还是不相等,继续往回找,找到一个位(a)跟第六位(a),相等,则在nextval[5]记录nextval[0]的值,即-1,这时如果子串跟主串的匹配在子串的第六位(a)匹配失败了,则直接略过主串的这一位,子串从头开始与主串的下一位继续进行匹配。
2{
3 int num=strlen(string);
4 int i=0,j=-1;
5 nextval[0]=-1;
6 while(i
8 if(j==-1||string[i]=string[j])
9 {
10i++;
11j++;
12if(string[i]==string[j])
13 {
14 nextval[i]=nextval[j];
15 }
16 else
17 {
18nextval[i]=j;
19 }
20 }
21 else
22 {
23 j=next[j];
24 }
25 }
kmp的思想主要是通过nextval数组来指示“假如在子串与主串匹配过程中在某一位(假设为 j )匹配失败(不相等)时,子串应回到的位置。”以此区别于朴素模式匹配的一旦在某位匹配失败,就从头比较的特点。所以在生成与子串等长的nextval数组时,nextval数组每一个元素标识的就应该是当在子串的第j位与主串匹配失败时,应回到子串的哪一位。
设子串string为"abqabc"。主串为"abqabqabc";生成nextval的思想是:假设目前 j 和 i 各处string的某一个位置,对比string[j]和string[i](代码第8行),若相等,j 和 i 都向前一步,j , i 向前一步(代码10~11行)是为了下一次匹配,同时是为了在nextval[i]记录当子串与主串匹配失败时应回到子串的哪一位继续比较下去(代码第14或18行)。比如说当子串与主串在第六位(子串的c跟主串的q)匹配失败时,我们会希望nextval[5]记录的是2,这样"ab"就不需重新匹配。
可以看到在子串的 c 之前,"abqab" 是前缀(ab)与后缀(ab)相等的,有两位,所以在nextval[5]记录 2 ,意思就是当 c 与主串匹配失败时,直接回到子串string[2]继续比较即可。
在制作nextval数组的过程中,i只会往前,j如果遇到前缀string[j]不等于后缀string[i]时会回溯,往回找,看能不能找到与后缀相等的前缀。比如子串为"abqabac",制作nextval数组时比较到第三位(q)跟第六位(a)时,此时q不等于a,所以j往回找,拿第二位(b)跟第六位(a)比较,还是不相等,继续往回找,找到一个位(a)跟第六位(a),相等,则在nextval[5]记录nextval[0]的值,即-1,这时如果子串跟主串的匹配在子串的第六位(a)匹配失败了,则直接略过主串的这一位,子串从头开始与主串的下一位继续进行匹配。
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯