《字符串模式匹配KMP算法》教学课例设计

计算机与信息学院 程玉胜 提供 KMP算法软件请联系：chengysh@aqtc.edu.cn

练习：求T=?AAAAAAAAAAB? 的模式函数值，并用后面的求模式函数值函数验证。 7 . next[n] 意义 ：

设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n], （1）、 next[n]= 0 表示S[m]和T[1]间接比较过了，不相等，下一次比较 S[m+1] 和

T[1]

（2）、 next[n]=1 表示比较过程中产生了不相等，下一次比较 S[m] 和T[1]。

（3）、 next[n]= k 表示S[m]的前k个字符与T中的开始k个字符已经间接比较相等

了，下一次比较S[m]和T[k]相等吗？

（4）、 其他值，不可能。 课后习题： 1. 2. 3. 4.

求串’ababaaababaa’ 的next函数值。 模式串t=’abcaabbcaabdab’，求模式串的next和nextval函数的值。 给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。 S=’aabcbabcaabcaaba’，T=’bca’，画出以T为模式串，S为目标串的匹配过程。

习题答案：

1. 求串’ababaaababaa’ 的next函数值。 【解答】 j 串 next[j] 1 a 0 2 b 1 3 a 1 4 b 2 5 a 3 6 a 4 7 a 2 8 b 2 9 a 3 10 11 12 b 4 a 5 a 6 2. 模式串t=’abcaabbcaabdab’，求模式串的next和nextval函数的值。 【解答】 j 串 next[j] 1 a 0 2 b 1 3 c 1 4 a 1 5 a 2 6 b 2 7 b 3 8 c 1 9 a 1 10 11 12 13 a 2 b 2 d 3 a 1 14 b 2

计算机与信息学院 程玉胜 提供 KMP算法软件请联系：chengysh@aqtc.edu.cn

nextval[j] 0 1 1 0 2 1 3 1 0 2 1 3 0 1 3.给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。 【解答】 j 串 next[j] nextval[j] 1 a 0 0 2 b 1 1 3 a 1 0 4 c 2 2 5 a 1 0 6 b 2 1 7 a 3 0 8 a 4 4 9 a 2 2 10 d 2 2 4． 对S=’aabcbabcaabcaaba’，T=’bca’，画出以T为模式串，S为目标串的匹配过程。 【解答】

bca的next值数为: 011 a a b c b a b c a a b c a a b a b c b

b c a b c b b c a