說明

以下算法介紹中，被匹配字符串稱為主串，匹配模式字符串稱為匹配串，索引從0開始。

前綴數(shù)組：字符串S = AB（B !== ?，即B為任一非空字符串) ，S的前綴指A。前綴數(shù)組指所有包含第一個字符但不包含最后一個字符的子串集合。

后綴數(shù)組：字符串S = AB（A !== ?，即A為任一非空字符串) ，S的后綴指B。后綴數(shù)組指所有包含最后一個字符但不包含第一個字符的子串集合。

一、BF

Brute Force 算法，簡稱BF。基本思想就是將主串第pos個字符與匹配串的第一個字符進(jìn)行比較，若相等，繼續(xù)將主串的下一個字符與匹配串的下一個字符進(jìn)行比較，若不相等，從主串的pos + 1 位置開始與匹配串的第一個字符進(jìn)行比較，重復(fù)前面的比較模式，直到得到結(jié)果。

假設(shè)主串長度為N，匹配串長度為M，該算法最壞的情況下需要進(jìn)行 M*(N-M) 次比較，算法時間復(fù)雜度為O(M*N)。

/*** @name bf* @param <String> s 主串* @param <String> m 匹配串* @return <Number> pos 返回匹配串在主串第一次出現(xiàn)的位置，若不存在，返回-1*/ function bf(s = '', m = '') {const lenS = s.lengthconst lenM = m.length// 首先將匹配串比主串長度還長及不符合題意的意外情況排除if(!lenS || !lenM || lenS < lenM) {return -1}// 注意一下邊界條件for(let pos = 0; pos < lenS - lenM + 1; pos++) {let j = 0while(j < lenM && s[pos + j] === m[j]) {j++}// 匹配完成if(j === lenM) {return pos}}return -1 }

二、KMP

Knuth-Morris-Pratt 算法，簡稱KMP，由 Donald Knuth，James H. Morris，Vaughan Pratt 1977年聯(lián)合發(fā)表。

BF 算法效率低在于每輪主串從pos位置開始比較過程中，若字符不相等，主串會回退到 pos+1 位置，然后與匹配串第一個位置字符開始比較。KMP 算法首先算出一個next 數(shù)組，匹配串每輪匹配在 j 位置失配時，匹配串向右滑動的距離為 j - next[j]。next 數(shù)組的計算規(guī)則如下。其中 j 為匹配串索引：

1、j = 0 時，next[j] = -1；

2、j > 0，匹配串0至 j-1 位置的子串前綴和后綴數(shù)組中最長相同元素的長度為maxL，則next[j] = maxL。特殊的，當(dāng) j=1時，前綴和后綴都為空，所以maxL=0，next[1] = 0；

/*** @name kmp* @param <String> s 主串* @param <String> m 匹配串* @return <Number> pos 返回匹配串在主串第一次出現(xiàn)的位置，若不存在，返回-1*/ function kmp(s = '', m = '') {const lenS = s.lengthconst lenM = m.lengthlet j = 0if(!lenS || !lenM || lenS < lenM) {return -1}const next = getNext(m)for(let pos = 0; pos < lenS - lenM + 1; pos++) {while(j < lenM && s[pos + j] === m[j]) {j++}// 匹配完成if(j === lenM) {return pos}// 匹配不完全，匹配串從next[j] 位置開始匹配j = next[j]}return -1 }/*** @name next* @param <String> m 需要求出next數(shù)組的匹配串* @return <Array> 返回next 數(shù)組*/ function getNext(m = '') {const len = m.lengthconst next = new Array(len).fill(0)next[0] = -1// 保存前綴和后綴數(shù)組最長相同子串let k = 0for(let j = 1; j < len - 1; j++) {while((k > 0) && (m[j - 1] !== m[k])) {k = next[j-1]}if((j > 1) && (m[j - 1] === m[k])) {k++}next[j] = k}return next }

二、BM

Boyer-Moore 算法，簡稱BM，由Robert S. Boyer 和 J Strother Moore 1977年發(fā)明。

當(dāng)在 i 位置字符失配，進(jìn)行下一輪匹配時，BF算法主串回退到 i+1 位置，匹配串回退到0位置。而KMP 算法主串不回退，匹配串自0位置向右滑動一定距離再進(jìn)行比較。顯然，匹配串向右滑動的距離越長，算法越高效。BM 算法從末尾開始匹配，根據(jù)以下兩條規(guī)則，計算得出的兩個數(shù)字取最大的一個為最終滑動距離：

1、壞字符規(guī)則

如上圖，匹配過程中，m 位置 j 的 c字符不等于a，所以c是壞字符。這時有兩種情況：

i、如果匹配串m的壞字符c左側(cè)位置 i（i < j）存在字符等于壞字符對應(yīng)主串中的a字符，則匹配m向右滑動距離為 j-i，即將位置 i 的字符與當(dāng)前壞字符對應(yīng)主串的字符對齊。

ii、如果匹配串m的壞字符左側(cè)不存在字符等于壞字符對應(yīng)的主串中的字符，則m向右滑動距離為 j+1。

2、好后綴規(guī)則

如上圖，匹配串從末尾開始匹配，匹配到m中的c不等于s中的a，則c是壞字符，而"ba"的所有子串都是好后綴，設(shè)為"ab"為 t，好后綴最大的索引為 i，即a 索引為i。這時也有兩種情況：

i、如果m的t左側(cè)存在子串 t' 使得 t'===t，則滑動m使得 t‘ 與 s中的 t 對齊。如果 t' ，則查找是否在 t 的某一個后綴 t2 左側(cè)存在子串 t3 等于t2 ，則滑動m 使得t3 與s 中對應(yīng)的t2 對齊。

iii、如果匹配串m 的好后綴左側(cè)都不存在符合第一種情況的子串，則整個匹配串向右滑動距離為 i+1。

后記

這篇文章感覺要爛尾了呀，時間線拖太長了。

很珍惜能來到tx 的機(jī)會，也很認(rèn)真地想把工作做好，反而如履薄冰，戰(zhàn)戰(zhàn)兢兢。還是喜歡灑脫的自己，只管全力以赴，其他的，不問、不求、不急，花開花謝，都是風(fēng)情。

總結(jié)

以上是生活随笔為你收集整理的列宽一字符等于多少厘米_字符串匹配算法总结——BF、KMP、BM的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。