數據結構-BF算法及KMP算法

jollywing 發布于2019-06-27 16:20 / 2449人閱讀

摘要：算法代碼復雜度最壞情況的時間復雜度。算法簡單記憶分為兩步模式串掃描，生成數組，。算法對算法的回溯問題進行了改進，在整個匹配過程中對主串僅需從頭至尾掃描一遍。在定義函數時在參數前加上改為引傳遞。一般情況為值傳遞，對象除外。

BF算法 代碼

= strlen($t)) $k = $i - strlen($t);
    else $k = -1;
    return $k;    
}
$str1 = "abaabcabclkjlkff";
$str2 = "abc";
echo bf($str1,$str2);
?>

復雜度

最壞情況的時間復雜度O(m*n)。m為模式串長度。n為目標串長度。

KMP算法 代碼

=strlen($t)) $v = $i - strlen($t);
    else $v = -1;
    return $v;
}

$s="ababcabcacbab";
$t="abcac";
$k;
$k = KMPIndex($s,$t);
echo $k;
?>

時間復雜度

時間復雜度為O(m+n)。m為模式串長度。n為目標串長度。
算法簡單記憶分為兩步:1.模式串掃描，生成next數組，O(m)。2.主串掃描，匹配，O(n)。
KMP算法對BF算法的回溯問題進行了改進，在整個匹配過程中對主串僅需從頭至尾掃描一遍。

其他

php函數參數傳遞。在定義函數時在參數前加上"&"改為引傳遞。一般情況為值傳遞，對象除外。

php在字符串索引某個字符。若包含中文字符需要另行處理。js可以通過"[]"直接索引。java用charat函數。

BM算法。

思考

看一個生成next數組的簡單例子。
考慮模式串t="abab",觀察一下next數組的生成過程。

初始化。j=0 k=-1 next[0]=-1

第一趟。j=1 k=0 next[1]=0

第二趟。k=next[0]=-1

第三趟。j=2 k=0 next[2]=0

第四趟。匹配。j=3 k=1 next[3]=1

第五趟。匹配。j=4 k=2 next[4]=2

這里首先可以注意到在第六步中j=4，而實際在我們的模式串"abab"中4這個下標已經越界了，嗯嗯，不要著急，我們先來看看在每一趟循環中到底做了什么。

        if($k==-1||$t[$j] == $t[$k]){
            $j++;
            $k++;
            $next[$j]=$k;
        }
        else $k = $next[$k];

代碼不過5行，一個if...else...的判斷語句。假設看的同學已經在其他地方看過這里前后綴的原理了。
如果k=-1或t[j]=t[k],j++,k++,next[j]=k。
這里的k=-1暫時不考慮他的作用，那么就是如果主串（模式串）與子串中的字符匹配，則主串指針向后一位，子串指針向后一位，給next數組賦值。
否則k=next[k]。否則向前移動子串指針。這里也是根據next數組移動子串指針并且需要注意抽象出子串的概念。

所以在第六步中匹配成功以后主串子串移動，在這之后已經跳出循環了。而實際上next[4]在目標串中匹配是用不到的。

嗯。。要記住是先嘗試匹配，成功后在向后移動指針，不匹配則重置指針。

這里的k=-1可以理解為當首位不匹配時移動指針的一個條件。

緊接著可以思考模式串"abcab"，"abcabd"，"ababab"等next數組的生成過程。理解kmp的重點在于next數組是如何生成的。

GPU云服務器云服務器 bf算法c語言‘’ kmp算法圖像識別 kmp算法php代碼字符串的kmp算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/22853.html

結合kmp算法的匹配動畫淺析其基本思想

摘要：寫在最前本次分享一下通過實現算法的動畫效果來試圖展示的基本思路。算法的關鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。本次主要通過動畫演示的方式展現樸素算法與算法對比過程的異同從而試圖理解的基本思路。寫在最前本次分享一下通過實現kmp算法的動畫效果來試圖展示kmp的基本思路。歡迎關注我的博客，不定期更新中—— 前置概念字符串匹配字符串匹配是計算...

wpw 2019-08-22 14:51 評論0 收藏0
字符串匹配算法之KMP模式

摘要：字符串的普通模式匹配普通模式匹配的原理不進行說明了，簡單來說就是兩個字符串的每個字符依次進行匹配。這篇文章主要是介紹KMP模式匹配算法，在正式介紹KMP之前我們先看一下普通模式匹配，由普通模式匹配在進一步的推導KMP模式會更容易理解。字符串的普通模式匹配普通模式匹配的原理不進行說明了，簡單來說就是兩個字符串的每個字符依次進行匹配。 public int match(String ...

NeverSayNever 2019-08-16 14:03 評論0 收藏0
KMP模式匹配算法（一）從暴力匹配切入

摘要：樸素的模式匹配算法這種算法又被稱為暴力匹配算法。如果匹配失敗，則回溯到主串的下一個位置重新逐位匹配。當然，在匹配算法中不同的輸入會有不同的復雜度，最好的情況就是一開始就匹配成功。切入結束，下篇詳解匹配算法最近在看關于算法方面的，正好看到關于KMP算法相關的部分，這里就做一個總結。假設我們有這樣的一個主串 S = googlgomglegoogle 和一個子串 C = google 我...

xfee 2019-08-22 10:37 評論0 收藏0