![](https://csdnimg.cn/release/download_crawler_static/19651060/bg1.jpg)
第 4 章 串
教材中练习题及参考答案
1. 串是一种特殊的线性表,请从存储和运算两方面分析它的特殊之处。
答:从存储方面看,串中每个元素是单个字符,在设计串存储结构时可以每个存储单
元或者结点只存储一个字符。从运算方面看,串有连接、判串相等、求子串和子串替换等
基本运算,这是线性表的基本运算中所没有的。
2. 为什么模式匹配中,BF 算法是有回溯算法,而 KMP 算法是无回溯算法?
答:设目标串为 s,模式串为 t。在 BF 算法的匹配过程中,当 t[j]=s[i]时,置 i++,j++;
当 t[j]≠s[i]时,置 i=i-j+1,j=0。从中看到,一旦两字符不等,目标串指针 i 会回退,所以
BF 算法是有回溯算法。在 KMP 算法的匹配过程中,当 t[j]=s[i]时,置 i++,j++;当 t[j]≠
s[i]时,i 不变,置 j=next[j]。从中看到,目标串指针 i 不会回退,只会保持位置不变或者向
前推进,所以 KMP 算法是无回溯算法。
3. 在 KMP 算法中,计算模式串的 next 时,当 j=0 时,为什么要置 next[0]=-1?
答:当模式串中 t
0
字符与目标串中某字符 s
i
比较不相等时,此时置 next[0]=-1 表示模
式串中已没有字符可与目标串的 s
i
比较,目标串当前指针 i 应后移至下一个字符,再和模
式串的 t
0
字符进行比较。
4. KMP 算法是简单模式匹配算法的改进,以目标串 s="aabaaabc"、模式串 t="aaabc"
为例说明的 next 的作用。
答:模式串 t="aaabc"的 next 数组值如表 4.1 所示。
表
4.1
模式串
t
对应的
next
数组
从 i=0,j=0 开始,当两者对应字符相等时,i++,j++,直到 i=2,j=2 时对应字符不相
等。如果是简单模式匹配,下次从 i=1,j=0 开始比较。
KMP 算法已经获得了前面字符比较的部分匹配信息,即 s[0..1]=t[0..1],所以 s[0]=t[0],
而 next[2]=1 表明 t[0]=t[1],所以有 s[0]=t[1],这说明下次不必从 i=1,j=0 开始比较,而只
需保持 i=2 不变,让 i=2 和 j=next[j]=1 的字符进行比较。
i=2,j=1 的字符比较不相等,保持 i=2 不变,取 j=next[j]=0。
i=2,j=0 的字符比较不相等,保持 i=2 不变,取 j=next[j]=-1。