數據結構c語言版嚴蔚敏清華大學出版社第四章串

模式匹配(定位) 設有主串S和子串T(將S稱為目標串，將T稱為模式串)，在主串S中，從位置start開始查找，如若在主串S中找到一個與子串T相等的子串，則返回T的第一個字符在主串中的位置，否則返回-1。 算法目的 確定主串中所含子串第一次出現的位置(定位) 算法種類 BF算法 (又稱古典的、經典的、樸素的、窮舉的) KMP算法 Brute-Force算法的設計思想： 將主串S的第一個字符和模式T的第1個字符比較， 若相等，繼續逐個比較后續字符； 若不等，從主串S的下一字符起，重新與T第一個字符比較。 直到主串S的一個連續子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。 否則，匹配失敗，返回值 –1。 BF算法的時間復雜度 討論： 若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數為(n-m+1)*m＝O(n*m) 最好的情況是：一配就中！ 只比較了m次。 最惡劣情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！所以總次數為：(n-m)*m+m ＝(n-m+1)*m KMP算法設計思想： 設s為主串，t為模式串，設i為主串s當前比較字符的下標，j為模式串t當前比較字符的下標，令i和j的初值為０。當si = tj時，i和j分別增1再繼續比較；否則 i不變，j改變為next[j]值(即模式串右滑)后再繼續比較。依次類推，直到出現下列兩種情況之一：一是 j退回到某個j=next[j]值時有si = tj ，則 i和j分別增1后再繼續比較；二是j退回到j=-1時，令主串和子串的下標各增1，隨后比較si+1和t0 。這樣的循環過程一直進行到變量大于等于S.length或變量j大于等于T.length時為止。 KMP算法的時間復雜度 注意：由于BF算法在一般情況下的時間復雜度也近似于O(n+m)，所以至今仍被廣泛采用。 第四趟匹配 ababcabcacbab abcac 第五趟匹配 ababcabcacbab a 第六趟匹配 ababcabcacbab abcac i=4 j=1 i=5 j=1 i=11 j=6 能否利用已部分匹配過的信息而加快模式串的滑動速度？ 能！而且主串S的指針i不必回溯！最壞情況也能達到O(n+m) 請看KMP算法！ 當模式串為,主串為’00000000000000000000000000000000000000000000000000001’時,整個匹配過程中指針i需回溯45次. a b a 盡量利用已經部分匹配的結果信息，盡量讓i不要回溯，加快模式串的滑動速度。 例： S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ 需要討論兩個問題： ①如何由當前部分匹配結果確定模式向右滑動的新比較起點k？ ② 模式應該向右滑多遠才是高效率的? i i i k k a b c k i i 2、KMP算法 T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ i k S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ i k 奇妙的結果： k 僅與模式串T有關！ 請抓住部分匹配時的兩個特征： 兩式聯立可得：“T0…Tk-1”=‘Tj-k …Tj-1’ 則T的k-1～０＝S前i-1～i-k)位 設目前打算與T的第k字符開始比較 (1) (2) ‘T０ … Tk-1’ 則T的j-1～j-k位＝ S前i-1～i-k)位 剛才肯定是在S的i處和T的第j字符 處失配 ‘Tj-k …Tj-1’ 截取一段，但k有限制，0

總結

以上是生活随笔為你收集整理的c语言实现bf算法的定位函数,数据结构c语言版严蔚敏清华大学出版社第四章串.ppt...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。