JavaScript 字符串匹配算法

[Checkson]

前言

字符串匹配算法，在日常开发中也常被频繁用到。当然，我们可以用正则匹配来完成字符串匹配，但是，学习和理解相关的字符串匹配算法，对于我们技术成长还是有很多好处的。

定义

字符串匹配算法，是在实际工程中经常遇到的问题，也是各大公司笔试面试的常考题目。此算法通常输入为原字符串（string）和子串（pattern），要求返回子串在原字符串中首次出现的位置。

1. BF算法

BF（Brute Force），暴力检索法是最好想到的算法，也最好实现。首先将原字符串和子串左端对齐，逐一比较；如果第一个字符不能匹配，则子串向后移动一位继续比较；如果第一个字符匹配，则继续比较后续字符，直至全部匹配。 时间复杂度：O(nm)。其中 n 为原字符串长度，m 为子串长度。

function BF (src, dest) {
    var len1 = src.length,
        len2 = dest.length;
    var i = 0,
        j = 0;
    while (i < len1 && j < len2) {
        if (src[i] === dest[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j === len2) {
        return i - j;
    }
    return -1;
}

2. RK算法

RK（Robin-Karp），哈希检索算法是对BF算法的一个改进：在BF算法中，每一个字符都需要进行比较，并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中，就尝试只进行一次比较来判定两者是否相等。 RK算法也可以进行多模式匹配，在论文查重等实际应用中一般都是使用此算法。

首先计算子串的HASH值，之后分别取原字符串中子串长度的字符串计算HASH值，比较两者是否相等：如果HASH值不同，则两者必定不匹配，如果相同，由于哈希冲突存在，也需要按照BF算法再次判定。

按照此例子，首先计算子串“DEF”Hash值为 Hd，之后从原字符串中依次取长度为3的字符串 “ABC”、“BCD”、“CDE”、“DEF”计算Hash值，分别为Ha、Hb、Hc、Hd，当 Hd 相等时，仍然要比较一次子串“DEF”和原字符串“DEF”是否一致。 时间复杂度：O(nm)（实际应用中往往较快，期望时间为O(n+m)）。

要实现RK算法，最重要的是怎么去选取Hash函数。这里我们选用前面章节 《JavaScript 散列》 中提到的“除留余数法”。

function hash (data) {
    var total = 0;
    for (var i = 0, len = data.length; i < len; i++) {
        total += 37 * total + data.charCodeAt(i);
    }
    total = total % 144451;
    return parseInt(total);
}

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 (src, dest) {
    if (!src || !dest) {
        retunr -1;
    }
    var len1 = src.length,
        len2 = dest.length;
    var destHash = hash(dest),
        index = -1;
    for (var i = 0; i <= len1 - len2; i++) {
        var subStr = src.substr(i, len2);
        if (hash(subStr) === destHash && isMatch(subStr, dest)) {
            index = i;
            break;
        }
    }
    return index;
}

3. KMP算法

KMP（Knuth-Morris-Pratt）算法，是字符串匹配最经典的算法之一，也是各大教科书上的看家绝学，曾被投票选为当今世界最伟大的十大算法之一，阮一峰老师也曾为KMP算法写过一篇博客：《字符串匹配的KMP算法》；但是这个算法被普遍认为隐晦难懂，而且十分难以实现。下面，我就不对KMP展开解释了，因为阮一峰老师的博客解释得足以通俗易懂。

在完成KMP算法之前，我们要解决最核心的问题是：部分匹配表的生成。部分匹配表，通俗点理解是，对于匹配串（dest）中所有字串的前缀和后缀匹配个数的分析。

function getNext (str) {
    var res = [];
    var k = 0;
    for (var i = 0, len = str.length; i < len; i++) {
        if (i === 0) {
            res.push(0);
            continue;
        }
        while (k > 0 && str[i] !== str[k]) {
            k = res[k - 1];
        }
        if (str[i] === str[k]) {
            k++;
        }
        res[i] = k;
    }
    return res;
}

这段代码的实现是用了DP（动态规划）思想，比较难理解。图例解释会比较直观，以字符串 “ABCDABD”为例：

KMP算法实现

function KMP (src, dest) {
    var next = getNext(dest);
    var len1 = src.length,
        len2 = dest.length;
    var i = 0,
        j = 0;
    while (i < len1 && j < len2) {
        if (src[i] === dest[j]) {
            i++;
            j++;
        } else {
            j = next[j - 1] || 0;
            i = i + (j > 0 ? 0 : 1);
        }
    }
    if (j === len2) {
        return i - j;
    }
    return -1;
}

4. BM 算法

前面提到的KMP算法，并不是效率最高的算法，实际采用并不多。各种文本编辑器的"查找"功能（Ctrl+F），大多采用的是Boyer-Moore算法。

Boyer-Moore算法不仅效率高，而且构思巧妙，容易理解。推荐阮一峰老师的博客教程《字符串匹配的Boyer-Moore算法》 来辅助大家理解，这里不展开讨论。

BM算法实现是较其他匹配算法复杂，它像是KMP算法和Sunday算法的结合体。

5. Sunday算法

BM算法并不是效率最高的算法，比它更快、更容易理解的还有Sunday算法，它有点像BM算法的删减版。

结合以上图例，可以用一句话来概括：当原字符串（src）和待查找字符串（dest）不匹配时，只需判断原字符串中下一个字符（THIS单词后的空格）是否出现在待查找字符串（dest）中；若存在，按照从右到左最先出现的位置偏移；若不存在，整体偏移 dest 的长度。

function getMoveLengthObj (str) {
    var resObj = {},
        len = str.length;
    for (var i = 0; i < len; i++) {
        resObj[str[i]] = len - i;
    }
    return resObj;
}

function Sunday (src, dest) {
    var moveObj = getMoveLengthObj(dest);
    var len1 = src.length,
        len2 = dest.length;
    var i = 0,
        j = 0;
    while (i < len1 && j < len2) {
        if (src[i] === dest[j]) {
            i++;
            j++;
        } else {
            i = i - j;
            var offset = moveObj[src[i + len2]];
            if (offset) {
                i += offset;
            } else {
                i += len2;
            }
            j = 0;
        }
    }
    if (j === len2) {
        return i - j;
    }
    return -1;
}

算法性能对比

名字	空间复杂度	最好时间复杂度	最差时间复杂度
BF算法	T(1)	O(nm)	O(nm)
RK算法	T(1)	O(n + m)	O(nm)
KMP算法	T(m)	O(n + m)	O(nm)
BM 算法	T(2m)	O(n)	O(nm)
Sunday算法	T(m)	O(n)	O(nm)

除上述字符串匹配算法外，还有一种更快的算法：

• Python版本（原版）：FlashText
• JavaScript版本：FlashText.js

参考链接

字符串匹配算法综述
BF、KMP、BM、Sunday算法讲解
Flashtext：大规模数据清洗的利器