SIVERSITY ScIE\CE TECH\OLoGY Homework 32.1 ■Page579:32.1-2,32.1-4
Homework 32.1 ◼ Page 579 : 32.1-2, 32.1-4
IVERSITY ScIE\CE TECH\OLoGY 8.2KMP算法 KMP算法思想:当遇到一个不成功匹配后,充分利用已经得 到的有关前一部分匹配的信息,避免多余的测试,加快匹配 过程。 在匹配过程过程中,文本串中的当前指针只会向右移(增加),不会向左倒 退 2在测试文本串的Ti+1.计m]这一段时,得到一个部分匹配:P[1.j= T[i+1.+j,但P+1]≠T+1; 3.设k是使得P[1.k]=P[〔j-k+1).j的最大整数(即P[I1.j中最长的与真 前缀相同的真后缀的长度) 4.定义: Nextli+1]=max{k+1|P[1.k是P[1.的后缀,j>k≥0} 5.Next函数值的计算只与模式串有关,与文本串内容无关,可以在进行匹 配前预先计算得到Next[1.m] 021/2 &T
2021/2/4 Department of Computer Science & Technology 17 8.2 KMP算法 ◼ KMP算法思想：当遇到一个不成功匹配后，充分利用已经得 到的有关前一部分匹配的信息，避免多余的测试，加快匹配 过程。 1. 在匹配过程过程中，文本串中的当前指针只会向右移(增加)，不会向左倒 退； 2. 在测试文本串的 T[i+1..i+m]这一段时，得到一个部分匹配： P[1..j] = T[i+1..i+j], 但 P[j+1] ≠ T[i+j+1]; 3. 设 k 是使得 P[1..k] = P[(j-k+1)..j]的最大整数（即 P[1..j]中最长的与真 前缀相同的真后缀的长度） 4. 定义: Next[j+1]= max{ k+1|P[1..k]是P[1..j]的后缀，j>k≥0 } 5. Next 函数值的计算只与模式串有关，与文本串内容无关，可以在进行匹 配前预先计算得到 Next[1..m]
IVERSITY ScIE\CE TECH\OLoGY KMP算法中的Next函数 CHINA Next(P[.m) 算法的运行时间为:O(m) 1.j←0; 1.由于i-j≥0,而且i-j单调增; 3.Fori+1tmd/3~j不变的次数不超过m 2.m← Length(P); i-j≤m,其增加的次数≤m。 4 Nexti]←j; 5. While j>0 and Pli]≠P[jdo j←Next]; j←j+1; 在《算法导论》一书中定义了另一种类似的函数r[i 两种函数之间的关系为:m[= Nexti+1]-1 021/2 18 &T
2021/2/4 Department of Computer Science & Technology 18 KMP算法中的Next函数 Next(P[1..m]) 1. j ← 0; 2. m ← Length(P) ; 3. For i ← 1 to m do 4. Next[i] ← j ; 5. While j > 0 and P[i]≠P[j] do 6. j ← Next[j] ; 7. j ← j + 1; 算法的运行时间为：O (m) 1. 由于 i - j ≥ 0， 而且 i - j 单调增； 2. i – j 不变的次数不超过m; 3. i – j ≤ m, 其增加的次数 ≤ m。 在《算法导论》一书中定义了另一种类似的函数 π[i]， 两种函数之间的关系为： π[i] = Next[i+1] -1
SIVERSITY ScIE\CE TECH\OLoGY KMP算法伪代码 CHINA 算法运行时间: o(n) KMPT, P) 由于i-j≥0,而且i-j单调增 不变的次数不超过n 2Fori←1 to n do 31-≤n其增加的次数≤n。 345 while>0 and Ti]* Pll do j←Next]; if j=m then //找到一个成功匹配 return i-m+1) j←j+1; 8 return (none) 021/2 &T
2021/2/4 Department of Computer Science & Technology 19 KMP算法伪代码 KMP(T, P) 1 j ← 1; 2 For i ← 1 to n do 3 while j > 0 and T[i] ≠ P[j] do 4 j ← Next[j] ; 5 if j = m then // 找到一个成功匹配 6 return (i-m+1) ; 7 j ← j +1 ; 8 return （none） 算法运行时间： O (n) 1. 由于 i - j ≥ 0， 而且 i - j 单调增； 2. i – j 不变的次数不超过n; 3. i – j ≤ n, 其增加的次数 ≤ n
SIVERSITY ScIE\CE TECH\OLoGY CHINA KMP.(T P) I n= Tienwh 2 m= P length 3 x=COMPUTE- PREFIX- FUNCTION(P) 0 A mumber of characers mathed 456789 5 for i= I ten A scan te ex from left to right while g>0 and Plg+ll≠Tl 4=h M next characer does not match if PH+l==Til q=q+1 ∥ next charset mattes 10 4== ∥ ss all of P matched? print"Paem occurs with shift i-m T ∥ kook for the nexI atch 021/2 &T
2021/2/4 Department of Computer Science & Technology 20