BF算法
BF（Brute Force），暴力檢索法是最好想到的算法，也最好實(shí)現(xiàn)。首先將原字符串和子串左端對齊，逐一比較；如果第一個(gè)字符不能匹配，則子串向后移動(dòng)一位繼續(xù)比較；如果第一個(gè)字符匹配，則繼續(xù)比較后續(xù)字符，直至全部匹配。 時(shí)間復(fù)雜度：O(nm)。其中 n 為原字符串長度，m 為子串長度。
function BF(haystack, needle) {
let j=0;
for(let i = 0; i < haystack.length; i++){
if(haystack[i] == needle[j]){
if(j == 0){
re = i;
}
j = j+1;
if(j == needle.length) {
return i-j+1;
}
}else {
if(j !== 0){
i=i-j;
}
j=0;
}
}
return -1;
}
RK算法
RK算法在BF基礎(chǔ)上，引入哈希算法。通過字符串的哈希值的比較替換掉字符串之間的比較，從而降低算法的時(shí)間復(fù)雜度。RK算法整體的時(shí)間復(fù)雜度為O(n)。其中 n 為原字符串長度。
// 生成hash值
function hash(string) {
let hash = 0;
for (let i = 0; i < string.length; i++) {
hash += 26 * hash + string[i].charCodeAt();
}
return hash;
}
// 比較兩個(gè)字符串是否相等
function isMatch (str, dest) {
if (str.length !== dest.length) {
return false;
}
for (var i = 0; i < str.length; i++) {
if (str[i] !== dest[i]) {
return false;
}
}
return true;
}
function RK(haystack, needle) {
let needleHash = hash(needle);
for(let i=0; i<=(haystack.length - needle.length); i++){
let subStr = haystack.substr(i, needle.length);
if (hash(subStr) === needleHash && isMatch(subStr, needle)) {
return i;
}
}
return -1;
}
BM算法
BM算法的核心思想是通過將模式串沿著主串大踏步的向后滑動(dòng)，從而大大減少比較次數(shù)，降低時(shí)間復(fù)雜度。而算法的關(guān)鍵在于如何兼顧步子邁得足夠大與無遺漏，同時(shí)要盡量提高執(zhí)行效率。這就需要模式串在向后滑動(dòng)時(shí)，遵守壞字符規(guī)則與好后綴規(guī)則，同時(shí)采用一些技巧。
壞字符
壞字符規(guī)則：從后往前逐位比較模式串與主串的字符，當(dāng)找到不匹配的壞字符時(shí)，記錄模式串的下標(biāo)值si，并找到壞字符在模式串中，位于下標(biāo)si前的最近位置xi（若無則記為-1），si-xi即為向后滑動(dòng)距離。（PS：我覺得加上xi必須在si前面，也就是比si小的條件，就不用擔(dān)心計(jì)算出的距離為負(fù)了）。但是壞字符規(guī)則向后滑動(dòng)的步幅還不夠大，于是需要好后綴規(guī)則。
好后綴
好后綴規(guī)則：從后往前逐位比較模式串與主串的字符，當(dāng)出現(xiàn)壞字符時(shí)停止。若存在已匹配成功的子串｛u｝，那么在模式串的｛u｝前面找到最近的｛u｝，記作｛u'｝。再將模式串后移，使得模式串的｛u'｝與主串的｛u｝重疊。若不存在｛u'｝，則直接把模式串移到主串的｛u｝后面。為了沒有遺漏，需要找到最長的、能夠跟模式串的前綴子串匹配的，好后綴的后綴子串（同時(shí)也是模式串的后綴子串）。然后把模式串向右移到其左邊界，與這個(gè)好后綴的后綴子串在主串中的左邊界對齊。
何時(shí)使用壞字符規(guī)則和好后綴規(guī)則呢？首先在每次匹配過程中，一旦發(fā)現(xiàn)壞字符，先執(zhí)行壞字符規(guī)則，如果發(fā)現(xiàn)存在好后綴，還要執(zhí)行好后綴規(guī)則，并從兩者中選擇后移距離最大的方案執(zhí)行。
技巧
1.通過散列表實(shí)現(xiàn)，壞字符在模式串中下標(biāo)位置的快速查詢。
2.每次執(zhí)行好后綴原則時(shí)，都會計(jì)算多次能夠與模式串前綴子串相匹配的好后綴的最長后綴子串。為了提高效率，可以預(yù)先計(jì)算模式串的所有后綴子串，在模式串中與之匹配的另一個(gè)子串的位置。同時(shí)預(yù)計(jì)算模式串中（同長度的）后綴子串與前綴子串是否匹配并記錄。在具體操作中直接使用，大大提高效率。
3.如何快速記錄模式串后綴子串匹配的另一個(gè)子串位置，以及模式串（相同長度）前綴與后綴子串石否匹配呢？先用一個(gè)suffix數(shù)組，下標(biāo)值k為后綴子串的長度，從模式串下標(biāo)為i（0~m-2）的字符為最后一個(gè)字符，查找這個(gè)子串是否與后綴子串匹配，若匹配則將子串起始位置的下標(biāo)值j賦給suffix[k]。若j為0，說明這個(gè)匹配子串的起始位置為模式串的起始位置，則用一個(gè)數(shù)組prefix，將prefix[k]設(shè)為true，否則設(shè)為false。k從0到m（模式串的長度）于是就得到了模式串所有前綴與后綴子串的匹配情況。
實(shí)現(xiàn)
僅有壞字符規(guī)則：
// 本例只實(shí)現(xiàn)從'a'-'z'的字符串匹配
function hashMap(needle) {
let hash = [];
for(let i=0; i<26; i++){
hash[i] = -1;
}
// 對于存在多個(gè)xi，則取靠后的那個(gè)下標(biāo)，防止滑動(dòng)過多
for(let i=0; i<needle.length; i++){
let ascii = needle[i].charCodeAt() - 97;
hash[ascii] = i;
}
return hash;
}
function BM(haystack, needle) {
let n = haystack.length;
let m = needle.length;
let hash = hashMap(needle);
let i = 0;
while(i <= n-m) {
let bad = -1;
for(let j = m-1; j>=0; j--){
if(haystack[i+j] !== needle[j]){
bad = j;
break;
}
};
if(bad === -1){
return i;
}
let ascii = haystack[bad+i].charCodeAt() - 97;
i = i + (bad - hash[ascii]);
}
return -1;
}
壞字符規(guī)則在某些場景下會使si-xi為負(fù)值，導(dǎo)致無限循環(huán)。如在“aaaaaaa”中匹配"baaaa"。
下面講好后綴原則加入，完整代碼如下：
function suffixAndPrefix(needle) {
let m = needle.length;
let suffix = [];
let prefix = [];
for(let i=0; i<m; i++){
suffix[i] = -1;
prefix[i] = false;
}
for(let i=0; i<m-1; i++){
let j=i;
let k=0;
while(j>=0 && needle[j] === needle[m-1-k]) {
j--;
k++;
suffix[k] = j+1;
}
if(j===-1){
prefix[k]=true;
}
}
return [suffix, prefix];
}
function moveByGoodFix(j, m, suffix, prefix) {
let k = m - 1 - j;
if(suffix[k] !== -1) return j - suffix[k] + 1; // 如果存在匹配的好后綴子集，滑動(dòng)到壞字符的下一位
// TODO 為什么要尋找？
for(let i=j+2; i<=m-1; i++) {
if(prefix[m-i] === true) {
return i;
}
}
return m;
}
function hashMap(needle) {
let hash = [];
for(let i=0; i<26; i++){
hash[i] = -1;
}
// 對于存在多個(gè)xi，則取靠后的那個(gè)下標(biāo)，防止滑動(dòng)過多
for(let i=0; i<needle.length; i++){
let ascii = needle[i].charCodeAt() - 97;
hash[ascii] = i;
}
return hash;
}
function BM(haystack, needle) {
let n = haystack.length;
let m = needle.length;
let [ suffix, prefix ] = suffixAndPrefix(needle);
let hash = hashMap(needle);
let i = 0;
while(i <= n-m) {
let bad = -1;
for(let j = m-1; j>=0; j--){
if(haystack[i+j] !== needle[j]){
bad = j;
break;
}
};
if(bad === -1){
return i;
}
let ascii = haystack[bad+i].charCodeAt() - 97;
let badChar = bad - hash[ascii];
let goodFix = 0;
// 判斷是否有好后綴
if(bad<m-1){
goodFix = moveByGoodFix(bad, m, suffix, prefix);
}
i = i + Math.max(badChar, goodFix);
}
return -1;
}
KMP算法
PMT數(shù)組
KMP算法的核心，是一個(gè)被稱為部分匹配表(Partial Match Table)的數(shù)組。
PMT中的值是字符串的前綴集合與后綴集合的交集中最長元素的長度。
next數(shù)組
為了編程的方便， 我們不直接使用PMT數(shù)組，而是將PMT數(shù)組向后偏移一位。我們把新得到的這個(gè)數(shù)組稱為next數(shù)組。
function next(needle) {
let res = [];
res[0] = -1;
let k = -1;
for (let i = 1; i < needle.length; i++) {
while (k != -1 && needle[i] != needle[k+1]) {
k = res[k]; // 當(dāng)不匹配的時(shí)候，回溯尋找次長串
}
if (needle[i] === needle[k+1]) {
k++;
}
res[i] = k;
}
return res;
}
function KMP(haystack, needle) {
let n = haystack.length;
let m = needle.length;
let nextArray = next(needle);
let j = 0;
for(let i=0; i<n; i++){
while(j>0 && haystack[i] !== needle[j]){
j = nextArray[j-1] + 1;
}
if(haystack[i] == needle[j]) {
j++;
}
if(j == m){
return i-m+1;
}
}
return -1;
}
算法比較
| 名稱 | 空間復(fù)雜度 | 最好時(shí)間復(fù)雜度 | 最差時(shí)間復(fù)雜度 |
|---|---|---|---|
| BF算法 | T(1) | O(nm) | O(nm) |
| RK算法 | T(1) | O(n+m) | O(nm) |
| BM算法 | T(2m) | O(n) | O(nm) |
| KMP算法 | T(m) | O(n+m) | O(nm) |
學(xué)習(xí)心得
BF算法是最容易想到的算法，只需要逐個(gè)字符去比較，遇到不匹配的字符只需要將主串字符向后移動(dòng)一位，重復(fù)比較即可。
RK算法在BF的基礎(chǔ)上，引入了hash值。核心理念是：hash值不相同的兩個(gè)字符串一定不想等，hash相等的字符串才有可能相等。通過hash值的運(yùn)算大大降低了字符比較的次數(shù)。
BM算法提出壞字符和好后綴的規(guī)則，從字符串的尾部開始比較。遇到壞字符則大幅度向后滑動(dòng)，好后綴規(guī)則是記錄模式串中前后是否有相同的部分。兩個(gè)規(guī)則中移動(dòng)距離比較遠(yuǎn)的，則成為下一次循環(huán)比較的開始。
KMP算法在BM算法的基礎(chǔ)上，直接先計(jì)算模式串的“重復(fù)度”即模式串的前后字符是否有相同的部分，匹配到不等的字符就可以把之前比較相等的部分跳過。
BM和KMP都是處理模式串本身，與主串無關(guān)。都是為了在下一次比較的時(shí)候能夠大幅度的向后移動(dòng)，以提高字符串匹配的速度。
