mirror of
https://github.com/Didnelpsun/CS408.git
synced 2026-02-07 21:04:38 +08:00
71 lines
2.8 KiB
Markdown
71 lines
2.8 KiB
Markdown
# 串习题
|
||
|
||
基本上就是考察$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$次。
|
||
|
||
## KMP算法优化
|
||
|
||
**例题** 串'$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]$。
|
||
|
||
编号|1|2|3|4|5|6|7|8|9|10|11|12
|
||
:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:
|
||
S|a|b|a|b|a|a|a|b|a|b|a|a
|
||
next|0|1|1|2|3|4|2|2|3|4|5|6
|
||
nextval|0|1|0|1|0|4|2|1|0|1|0|4
|