串习题

基本上就是考察$KMP$算法

KMP算法

例题设主串$T=$'$abaabaabcabaabc$'，模式串$S=$'$abaabc$'，采用$KMP$算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是()。

A.9

B.10

C.12

D.15

解：$B$。假设位序从$0$开始。

编号	0	1	2	3	4	5
S	a	b	a	a	b	c
next	-1	0	0	1	1	2

第一趟连续比较$6$次，在模式串的$5$号位和主串的$5$号位匹配失败，模式串的下一个比较位置为$next[5]$，即下一次比较从模式串的$2$号位和主串的$5$号位开始，然后直到模式串$5$号位和主串$8$号位匹配，第二趟比较$4$次，模式串匹配成功。单个字符的比较次数为$10$次。

例题串'$ababaaababaa$'的$nextval$数组为()。

A.0,1,0,1,1,2,0,1,0,1,0,2

B.0,1,0,1,1,4,1,1,0,1,0,2

C.0,1,0,1,0,4,2,1,0,1,0,4

D.0,1,1,1,0,2,1,1,0,1,0,4

解：$C$。$nextval$从$0$开始，可知串的位序从$1$开始（若从$0$开始。则第一个是$-1$）。第一步，令$nextval[1]=next[1]=0$。

从$j=2$开始，依次判断$p_j$是否等于$p_{next[j]}$，否则将$next[j]$修正为$next [next[j]]$，直至两者不相等为止。

第$2$步: $p_2=b$、$p_{next[2]}=a$，$p_2\neq p_{next [2]}$，$nextval[2]=next[2]=1$。

第$3$步: $p_3=a$、$p_{next[3]}=a$，$p_3=p_{next[3]}$，$nextval[3]=nextval [next[3]]=nextval[1]=0$。

第$4$步: $p_4=b$、$p_{next[4]}=b$，$p_4=p_{next[4]}$，$nextval[4]=nextval[next[4]]=nextval[2]=1$。

第$5$步: $p_5=a$、$p_{next[5]}=a$，$p_5=p_{next[5]}$，$nextval[5]=nextval[next[5]]=nextval[3]=0$。

第$6$步: $p_6=a$、$p_{next[6]}=b$，$p_6\neq p_{next [6]}$，$nextval[6]=next[6]=4$。

第7步：$p_7=a$、$p_{next [7]}=b$，$p_7\neq p_{next [7]}$，$nextval[7]=next[ 7]=2$。

第$8$步: $p_e=b$、$p_{next[8]}=b$，$p_8=p_{next[8]}$，$nextval[8]=nextval[next[8]]=nextval[2]=1$。

第$9$步: $p_9=a$、$p_{next[9]}=a$，$p_9=p_{next[9]}$，$nextval[9]=nextval [next[9]]=nextval[3]=0$。

第$10$步：$p_{10}=b$、$p_{next[10]}=b$，$p_{10}=p_{next[10]}$，$nextval[10]=nextval[next[10]]=nextval[4]=1$。

第$11$步: $p_{1=a}$、$p_{next[11]}=a$，$p_{11}=p_{next(11]}$，$nextval[11]=nextval[next[11]]=nextval[5]=0$。

第$12$步：$p_{12}=a$、$p_{next[12]}=a$，$p_{10}=p_{next[12]}$，$nextval[12]=nextval[next[12]]=nextval[6]=4$。

在第$5$步的推理中，$p_5=p_{next[5]}=a$，按前面的讲解部分，应该继续让$p_3$和$p_{next[3]}$比较（恰好$p_3=p_{next[3]}=1$），注意到此时$nextval[3]的值已存在，故直接将nextval[5]赋值为nextval[3]$。