首页 > 试题广场 >

已知主串s=’ADBADABBAABADABBADADA’,

[问答题]
已知主串s=’ADBADABBAABADABBADADA’,
模式串pat=’ADABBADADA',
写出模式串的nextval函数值,并由此画出KMP算法匹配的全过程。
模式串pat ADABBADADA
next数组
0112112341
nextval数组
0102101040
注求法:
next数组的求解方法是:
1.第一位的next值为0
2.第二位的next值为1
后面求解每一位的next值时,根据前一位进行比较
3.第三位的next值:第二位的模式串为b ,对应的next值为1;将第二位的模式串b与第一位的模式串a进行比较,不相等;则第三位的next值为1(其他情况均为1)
4.第四位的next值:第三位的模式串为a ,对应的next值为1;将第三位的模式串a与第一位的模式串a进行比较,相同,则第四位的next值得为1+1=2
5.第五位的next值:第四位的模式串为a,对应的next值为2;将第四位的模式串a与第二位的模式串b进行比较,不相等;第二位的b对应的next值为1,则将第四位的模式串a与第一位的模式串a进行比较,相同,则第五位的next的值为1+1=2
6.第六位的next值:第五位的模式串为b,对应的next值为2;将第五位的模式串b与第二位的模式中b进行比较,相同,则第六位的next值为2+1=3
7.第七位的next值:第六位的模式串为c,对应的next值为3;将第六位的模式串c与第三位的模式串a进行比较,不相等;第三位的a对应的next值为1,
则将第六位的模式串c与第一位的模式串a进行比较,不相同,则第七位的next值为1(其他情况)
8.第八位的next值:第七位的模式串为a,对应的next值为1;将第七位的模式串a与第一位的模式串a进行比较,相同,则第八位的next值为1+1=2
9.第八位的next值:第八位的模式串为b,对应的next值为2;将第八位的模式串b与第二位的模式串b进行比较,相同,则第九位的next值为2+1=3
如果位数更多,依次类推
nextVal数组的求解方法:

1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。 
 2.第三位的next值为1,那么将第三位和第一位进行比较,均为a,相同,则,第三位的nextval值为0。 
  3.第四位的next值为2,那么将第四位和第二位进行比较,不同,则第四位的nextval值为其next值,为2。
   4.第五位的next值为2,那么将第五位和第二位进行比较,相同,第二位的next值为1,则继续将第二位与第一位进行比较,不同,则第五位的nextval值为第二位的next值,为1。
    5.第六位的next值为3,那么将第六位和第三位进行比较,不同,则第六位的nextval值为其next值,为3。
    6.第七位的next值为1,那么将第七位和第一位进行比较,相同,则第七位的nextval值为0。
    7.第八位的next值为2,那么将第八位和第二位进行比较,不同,则第八位的nextval值为其next值,为2。
发表于 2020-01-04 15:43:51 回复(1)
模式串pat ADABBADADA
next数组 0112112343
nextval数组 0102101040

编辑于 2018-06-13 16:35:49 回复(4)
网上没找到表格的写法 不知道格式是否正确
发表于 2022-12-03 12:37:24 回复(0)