華北水利學院數據結構課件第四章(陳波)(編輯修改稿)
2025-01-18 23:45 本頁面
【文章內容簡介】 ab， 模式 T=abcac 4. 串的應用 ——BF模式匹配算法 1. 在串 S和串 T中設比較的起始下標 i和 j； 2. 循環(huán)直到 S或 T的所有字符均比較完； 如果 S[i]=T[j]， 繼續(xù)比較 S和 T的下一個字符； 否則 ， 將 i和 j回溯 ， 準備下一趟比較； 3. 如果 T中所有字符均比較完 ， 則匹配成功 ， 返回匹配的起始比較下標；否則 ， 匹配失敗 ， 返回 0； 4. 串的應用 ——BF模式匹配算法 int BFmatching(char s[ ], char t[ ]) { i=1。 j=1。 while (i=s[0]j=t[0]) { if (s[i]==t[j]) { i++。 j++。 } else { i=ij+2。 j=1。 } } if (jt[0]) return (ij+1)。 else return 0。 } 4. 串的應用 ——BF模式匹配算法 4. 串的應用 ——BF模式匹配算法 ? 設串 s長度為 n，串 t長度為 m，在匹配成功的情況下，考慮兩種極端情況： ? 最好情況 ：不成功的匹配都發(fā)生在串 t的第一個字符。 ? 例如： s=aaaaabcd t=bcd ? 設匹配成功發(fā)生在 si處，則在 i1趟不成功的匹配中共比較了i1次，第 i趟成功的匹配共比較了 m次，所以總共比較了 i1+m次，所有匹配成功的可能情況共有 nm+1種，則：設從 si開始與 t串匹配成功的概率為 pi，在等概率情況下pi=1/(n?m+1)，平均比較的次數是 ? 因此最好情況下的時間復雜度是 O(n+m)。 11 1 ( )( 1 ) ( 1 )12n m n miiinmp i m i mnm? ? ? ????? ? ? ? ? ? ? ????? 4. 串的應用 ——BF模式匹配算法 ? 設串 s長度為 n，串 t長度為 m，在匹配成功的情況下，考慮兩種極端情況： ? 最壞情況 ：不成功的匹配都發(fā)生在串 t的最后一個字符。 ? 例如： s=aaaaab t= aaab“ ? 設匹配成功發(fā)生在 si處，則在 i1趟不成功的匹配中共比較了 (i1) m次，第 i趟成功的匹配共比較了m次，所以總共比較了 i m次，因此平均比較的次數是 ? 一般情況下， mn，因此最壞情況下的時間復雜度是 O(nm)。 11 1 ( 2)( ) ( )12in m n miim n mp i m i mnm? ? ? ???? ? ?? ? ? ? ? ????? 4. 串的應用 ——BF模式匹配算法 ? 為什么 BF算法時間性能低？ ? 在每趟匹配不成功時存在大量回溯，沒有利用已經部分匹配的結果。 ? 如何在匹配不成功時主串不回溯？ ? 主串不回溯，模式就需要向右滑動一段距離。 ? 如何確定模式的滑動距離？ i=3， j=3失敗； s2=t2。t1≠t2 ∴ t1≠s2 a b a b c a b c a c b a b i j 第 1 趟 a b c a c a b a b c a b c a c b a b 第 2 趟 a b c a c 4. 串的應用 ——KMP模式匹配算法 i=3， j=3失?。? s2=t2。t1≠t2 ∴ t1≠s2 a b a b c a b c a c b a b i j 第 1 趟 a b c a c a b a b c a b c
物理相關推薦
鄂ICP備17016276號-1