第3章特殊线性表—栈、队列与串.ppt

请抓住部分匹配时的两个特征： （1）设模式滑动到第k个字符，则T1～Tk-1 ＝Si-(k-1) ～ Si-1 S=a b a b c a b c a c b a b T=a b c a c i k j S=a b a b c a b c a c b a b T=a b c a c i k 特殊线性表——串 模式匹配——KMP算法 请抓住部分匹配时的两个特征： 两式联立可得：T1～Tk-1＝Tj-(k-1) ～Tj-1 （2）则Tj-(k-1) ～ Tj-1 ＝Si-(k-1) ～ Si-1 S=a b a b c a b c a c b a b T=a b c a c i k j i S=a b a b c a b c a c b a b T=a b c a c j k 特殊线性表——串 模式匹配——KMP算法 （1）设模式滑动到第k个字符，则T1～Tk-1 ＝Si-(k-1) ～ Si-1 T1…Tk-1＝Tj-(k-1) …Tj-1说明了什么？ （1） k 与 j 具有函数关系，由当前失配位置 j ，可以计算出滑动位置 k（即比较的新起点）； （2）滑动位置k 仅与模式串T有关。 从第1位往右 经过k-1位 从j-1位往左 经过k-1位 k＝max { k |1kj 且T1…Tk-1＝Tj-(k-1) …Tj-1 } T1…Tk-1＝Tj-(k-1) …Tj-1的物理意义是什么？ 模式应该向右滑多远才是最高效率的? 特殊线性表——串 模式匹配——KMP算法 next[ j ]＝ 0 当j＝1时 //不比较 max { k | 1kj 且T1…Tk-1=Tj-(k-1) …Tj-1 } 1 其他情况 令k = next[ j ]，则： next[j]函数表征着模式T中最大相同首子串和尾子串（真子串）的长度。 可见，模式中相似部分越多，则next[j]函数越大，它既表示模式 T 字符之间的相关度越高，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。 特殊线性表——串 模式匹配——KMP算法 当j=1时，next[j]=0； //next[j]=0表示根本不进行字符比较 当j1时，next[j]的值为：模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度加1。 当无首尾相同的子串时next[j]的值为1。 //next[j]=1表示从模式串头部开始进行字符比较 （2）计算next[j]的方法： 特殊线性表——串 模式匹配——KMP算法 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位k=next[j] : 0 1 1 2 2 3 1 2 j=1时, next[ j ]＝ 0； j=2时, next[ j ]＝ 1； j=3时, T1≠T2，因此，k=1； j=4时, T1＝T3，因此，k=2； j=5时, T1＝T4，因此，k=2； 以此类推。 特殊线性表——串 模式匹配——KMP算法 T=a b a a b a b c S=a b a b c a b a a b c a a b a a b a b c a a b 作业： 1. 已知： 2. 设输入元素为1,2,3,a,b，输入次序为123ab，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可作为高级语言变量名。 求模式T的next[j]，写出KMP匹配过程。 在串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]; } 求模式串T的n