資訊專欄INFORMATION COLUMN
摘要：算法代碼復(fù)雜度最壞情況的時(shí)間復(fù)雜度。算法簡單記憶分為兩步模式串掃描，生成數(shù)組，。算法對(duì)算法的回溯問題進(jìn)行了改進(jìn)，在整個(gè)匹配過程中對(duì)主串僅需從頭至尾掃描一遍。在定義函數(shù)時(shí)在參數(shù)前加上改為引傳遞。一般情況為值傳遞，對(duì)象除外。
BF算法 代碼
= strlen($t)) $k = $i - strlen($t);
else $k = -1;
return $k;
}
$str1 = "abaabcabclkjlkff";
$str2 = "abc";
echo bf($str1,$str2);
?>
復(fù)雜度
最壞情況的時(shí)間復(fù)雜度O(m*n)。m為模式串長度。n為目標(biāo)串長度。
KMP算法 代碼=strlen($t)) $v = $i - strlen($t);
else $v = -1;
return $v;
}
$s="ababcabcacbab";
$t="abcac";
$k;
$k = KMPIndex($s,$t);
echo $k;
?>
時(shí)間復(fù)雜度
時(shí)間復(fù)雜度為O(m+n)。m為模式串長度。n為目標(biāo)串長度。
算法簡單記憶分為兩步:1.模式串掃描，生成next數(shù)組，O(m)。2.主串掃描，匹配，O(n)。
KMP算法對(duì)BF算法的回溯問題進(jìn)行了改進(jìn)，在整個(gè)匹配過程中對(duì)主串僅需從頭至尾掃描一遍。
php函數(shù)參數(shù)傳遞。在定義函數(shù)時(shí)在參數(shù)前加上"&"改為引傳遞。一般情況為值傳遞，對(duì)象除外。
php在字符串索引某個(gè)字符。若包含中文字符需要另行處理。js可以通過"[]"直接索引。java用charat函數(shù)。
BM算法。
思考看一個(gè)生成next數(shù)組的簡單例子。
考慮模式串t="abab",觀察一下next數(shù)組的生成過程。
初始化。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，而實(shí)際在我們的模式串"abab"中4這個(gè)下標(biāo)已經(jīng)越界了，嗯嗯，不要著急，我們先來看看在每一趟循環(huán)中到底做了什么。
if($k==-1||$t[$j] == $t[$k]){
$j++;
$k++;
$next[$j]=$k;
}
else $k = $next[$k];
代碼不過5行，一個(gè)if...else...的判斷語句。假設(shè)看的同學(xué)已經(jīng)在其他地方看過這里前后綴的原理了。
如果k=-1或t[j]=t[k],j++,k++,next[j]=k。
這里的k=-1暫時(shí)不考慮他的作用，那么就是如果主串（模式串）與子串中的字符匹配，則主串指針向后一位，子串指針向后一位，給next數(shù)組賦值。
否則k=next[k]。否則向前移動(dòng)子串指針。這里也是根據(jù)next數(shù)組移動(dòng)子串指針并且需要注意抽象出子串的概念。
所以在第六步中匹配成功以后主串子串移動(dòng)，在這之后已經(jīng)跳出循環(huán)了。而實(shí)際上next[4]在目標(biāo)串中匹配是用不到的。
嗯。。要記住是先嘗試匹配，成功后在向后移動(dòng)指針，不匹配則重置指針。
這里的k=-1可以理解為當(dāng)首位不匹配時(shí)移動(dòng)指針的一個(gè)條件。
緊接著可以思考模式串"abcab"，"abcabd"，"ababab"等next數(shù)組的生成過程。理解kmp的重點(diǎn)在于next數(shù)組是如何生成的。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/22853.html
摘要：寫在最前本次分享一下通過實(shí)現(xiàn)算法的動(dòng)畫效果來試圖展示的基本思路。算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。本次主要通過動(dòng)畫演示的方式展現(xiàn)樸素算法與算法對(duì)比過程的異同從而試圖理解的基本思路。 寫在最前 本次分享一下通過實(shí)現(xiàn)kmp算法的動(dòng)畫效果來試圖展示kmp的基本思路。 歡迎關(guān)注我的博客，不定期更新中—— 前置概念 字符串匹配 字符串匹配是計(jì)算...
摘要：字符串的普通模式匹配普通模式匹配的原理不進(jìn)行說明了，簡單來說就是兩個(gè)字符串的每個(gè)字符依次進(jìn)行匹配。 這篇文章主要是介紹KMP模式匹配算法，在正式介紹KMP之前我們先看一下普通模式匹配，由普通模式匹配在進(jìn)一步的推導(dǎo)KMP模式會(huì)更容易理解。 字符串的普通模式匹配 普通模式匹配的原理不進(jìn)行說明了，簡單來說就是兩個(gè)字符串的每個(gè)字符依次進(jìn)行匹配。 public int match(String ...
摘要：樸素的模式匹配算法這種算法又被稱為暴力匹配算法。如果匹配失敗，則回溯到主串的下一個(gè)位置重新逐位匹配。當(dāng)然，在匹配算法中不同的輸入會(huì)有不同的復(fù)雜度，最好的情況就是一開始就匹配成功。切入結(jié)束，下篇詳解匹配算法 最近在看關(guān)于算法方面的，正好看到關(guān)于KMP算法相關(guān)的部分，這里就做一個(gè)總結(jié)。假設(shè)我們有這樣的一個(gè)主串 S = googlgomglegoogle 和一個(gè)子串 C = google 我...
閱讀 1256·2023-04-26 00:47
閱讀 3601·2021-11-16 11:53
閱讀 824·2021-10-08 10:05
閱讀 2785·2021-09-22 15:19
閱讀 3002·2019-08-30 15:55
閱讀 2780·2019-08-29 16:55
閱讀 2960·2019-08-29 15:20
閱讀 1133·2019-08-23 16:13
