[工学]第三章串3.ppt

第3章 特殊线性表——串 第3章 特殊线性表——串 第3章 特殊线性表——串 计算Next[j]的方法： 当j=1时，Next[j]=0； //Next[j]=0表示根本不进行字符比较 当j1时，Next[j]的值为：模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度加1。 无首尾相同的子串时Next[j]的值为1。 // Next[j]=1表示从模式串头部开始进行字符比较 （2） next[ j ]怎么计算？ 怎样计算模式T所有可能的失配点 j 所对应的 next[j]？ 从两头往中间比较 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位k=next[j] : next[ j ]＝ 0 当j＝1时 max { k |1kj 且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ } 1 其他情况 0 1 2 2 3 1 2 讨论： j=1时, next[ j ]≡ 0；//属于“j=1”情况; j=2时, next[ j ]≡ 1；// 找不到1kj的k，属于“其他情况”； 刚才已归纳： j=3时, k={2}，只需查看‘T1’=‘T2’成立否，No则属于其他情况 j=4时, k={2，3}，要查看‘T1’=‘T3’ 及‘T1T2’=‘T2 T3’ 是否成立 j=5时, k={2，3，4}，要查看‘T1’=‘T4’ ，‘T1T2’=‘T3T4’ 和 ‘T1T2T3’=‘T2T3T4’是否成立 以此类推，可得后续next[j]值。 next[j]与s无关，可以预先计算 例： 1 第3章 特殊线性表——串 在串S和串T中分别设比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如果S[i]=T[j]，继续比较S和T的下一个字符；否则 2.2 将j向右滑动到next[j]位置，即j=next[j]； 2.3 如果j=0，则将i和j分别加1，准备下一趟比较； 3. 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0； KMP算法用伪代码描述 void GetNext(char T[ ], int next[ ]) { next[1]=0; j=1; k=0; while (jT[0]) if ((k==0)| |(T[j]= =T[k])) { j++; k++; next[j]=k; } else k=next[k]; } 第3章 特殊线性表——串 求模式串T的next函数值算法 第3章 特殊线性表——串 求next数组的算法只需将模式扫描一遍，设模式串的长度为m，则算法的时间复杂度为O(m)。而KMP算法的时间复杂度为O(n+m)。KMP算法与BF算法相比，增加了很大的难度，我们主要学习该算法的设计技巧。 a b a b c a b c a c b a b a b c i j i j i j 第一趟，i=3，j=3失败，i不动 next[3]=1，j滑动到1的位置 a b a b c a b c a c b a b a b c a c i j i j i j i j i j 第二趟i=7，j=5失败，i不动 next[5]=2，j滑动到2的位置 * 第3章 特殊线性表—栈、队列和串 本章的基本内容是： ⑴栈和队列的定义及操作特性； 　⑵栈和队列的两种存储方法和基本运算的实现； 　⑶串的基本概念和操作； 　⑷串的常用存储方法； 　⑸串的模式匹配算法。 第3章 特殊线性表——串 3.3.1 串的逻辑结构 1. 串的定义 串是零个或多个字符组成的有限序列 。 空格串：只包含空格的串。 串的长度 ：串中所包含的字符个数。 空串：长度为0的串。 空串记作 “ ”； 非空串通常记作：S=“s1 s2 …… sn” 其中：S是串名；双引号是定界符 ；双引号引起来的部分是串值 。si（1≤i≤n）是一个任意字符。 第3章