Netherspite

字符串匹配分为单模式串匹配和多模式串匹配，主串是被匹配串，模式串是要在主串中检索的字符串。

Brute Force

BF算法即暴力匹配算法，在主串中，检查起始位置分别是0、1、…、n-m且长度为m的n-m+1个子串，看有没有和模式串匹配的，时间复杂度是$O(mn)$。虽然时间复杂度比较高，但在实际开发中比较常用，因为实际开发中模式串和主串的长度都不会太长，而且每次匹配不会遍历m个字符，在中间不同就会停止，所以执行效率要比$O(mn)$高很多。其次，这种算法思想简单，实现也简单，有bug容易暴露和修复，符合KISS（Keep it Simple and Stupid）设计原则，即在满足性能要求的前提下，简单是首选。

Rabin-Karp

RK算法在BF算法的基础上，引入哈希算法，通过哈希算法对主串中n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比大小。哈希值是数字，提高了模式串和子串比较的效率。

假设要匹配的字符串的字符集中只包含K个字符，可以用一个K进制数来表示一个子串，再把这个K进制数转化成十进制数，作为子串的哈希值。比如字符集是a-z这26个字符，一个字符串可以表示为：
$$
“cba” = “c”\times26\times26+”b” \times26+”a”
$$
这种哈希算法是没有散列冲突的，并且前后相邻的字符串的哈希值是有规律相关的，计算比较简单，但计算出来的值可能很大。

有散列冲突的算法也可以工作，当散列值相等时只需要再比较一下子串和模式串是否相等即可，一般情况下，冲突不会很多，RK的算法效率比BF高。

Boyer-Moore

BM算法包含两部分，分别是坏字符规则和好后缀规则。

Bad Character Rule

BM算法的匹配顺序是按照模式串下标从大到小倒着匹配的，当发现某个字符没法匹配的时候，把这个没有匹配的字符叫作坏字符（主串中的），拿坏字符在模式串中查找，若模式串中不存在这个字符，这时将模式串向后滑动到该坏字符的后面，再从末尾开始匹配；若模式串中存在这个字符，则向后滑动让这两个字符对齐，再从末尾重新匹配，若存在多个坏字符，则选择最靠后的那个。坏字符对应的模式串中的字符下标记作si，坏字符在模式串的下标为xi，如果不存在记为-1，模式串往后移的位数等于si-xi。

Good Suffix Shift

已经匹配的后缀{u}叫作好后缀，拿它在模式串中查找，如果找到了另一个与之相匹配的子串{u*}，则将模式串滑动到子串{u*}与主串{u}对齐的位置。如果找不到另一个等于{u}的子串，就直接将模式串滑动到主串中{u}的后面，在滑动过程中，当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。从好后缀的后缀子串中，找到一个最长且能跟模式串的前缀子串匹配的，将模式串滑动到其前缀子串与主串中好后缀的后缀子串对齐的位置。

算法实现

拿坏字符在模式串中顺序遍历查找比较低效，可以将模式串中的每个字符及其下标存储到散列表中，这样就可以快速找到坏字符在模式串的下标。

const SIZE = 256;	//坏字符散列表的大小
let bc = Array(SIZE).fill(-1);//坏字符散列表，初始化为-1
function generateBC(pattern, bc) {
  for(let i = 0; i < pattern.length; i++) {
    let ascii = pattern.charCodeAt(i);//模式串每一位的ASCII码
    bc[ascii] = i;
  }
}
function bm(str, pattern) {
  const n = str.length, m = pattern.length;
  generateBC(pattern, bc);//构建坏字符散列表
  let i = 0;//表示主串与模式串对齐的第一个字符
  while(i <= n - m) {
    let j;
    for(j = m - 1; j >= 0; --j) {//模式串从后往前匹配
      if(str[i + j] !== pattern[j]) break; //坏字符对应模式串的下标是j
    }
    if(j < 0) return i;//匹配成功，返回主串与模式串第一个匹配的字符的位置
    i = i + (j - bc[str.charCodeAt(i + j)]);
  }
  return -1;
}

好后缀引入变量suffix数组，suffix数组的下标k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀相匹配的子串{u*}的起始下标位置。prefix数组记录模式串的后缀子串是否能匹配模式串的前缀子串。比如模式串cabcab：

后缀子串 长度 suffix prefix
b 1 suffix[1] = 2 prefix[1] = false
ab 2 suffix[2] = 1 prefix[2] = false
cab 3 suffix[3] = 0 prefix[3] = true
bcab 4 suffix[4] = -1 prefix[4] = false
abcab 5 suffix[5] = -1 prefix[5] = false 
function generateGS(pattern, suffix, prefix) {
  const m = pattern.length;
  for(let i = 0; i < m; i++) {//初始化
    suffix[i] = -1;
    prefix[i] = false;
  }
  for(let i = 0; i < m - 1; i++) {
    let j = i, k = 0;//k为公共后缀子串长度
    while(j >= 0 && pattern[j] === pattern[m - 1 - k]) {//与pattern[0, m - 1]求公共后缀子串
      j--;
      k++;
      suffix[k] = j + 1;//j + 1表示公共后缀子串在pattern[0, i]中的起始下标
    }
    if(j === -1) prefix[k] = true;//如果公共后缀子串也是模式串的前缀子串
  }
}

假设好后缀的长度是k，先拿好后缀在suffix数组中查找其匹配的字符串，如果suffix[k]不等于-1，则将模式串向后移动j - suffix[k] + 1位，j表示坏字符对应的模式串中的字符下标。如果suffix[k]等于-1，则如果有prefix[k] = true，k = m - r，r为j + 2到m - 1，则向后移动r位。如果两个都不符合，则向后移m位。此时完整的代码如下：

const SIZE = 256;	//坏字符散列表的大小
let bc = Array(SIZE).fill(-1);//坏字符散列表，初始化为-1
function generateBC(pattern, bc) {
  for(let i = 0; i < pattern.length; i++) {
    let ascii = pattern.charCodeAt(i);//模式串每一位的ASCII码
    bc[ascii] = i;
  }
}
function bm(str, pattern) {
  const n = str.length, m = pattern.length;
  generateBC(pattern, bc);//构建坏字符散列表
  let suffix = Array(m), prefix = Array(m);
  generateGS(pattern, suffix, prefix);
  let i = 0;//表示主串与模式串对齐的第一个字符
  while(i <= n - m) {
    let j;
    for(j = m - 1; j >= 0; --j) {//模式串从后往前匹配
      if(str[i + j] !== pattern[j]) break; //坏字符对应模式串的下标是j
    }
    if(j < 0) return i;//匹配成功，返回主串与模式串第一个匹配的字符的位置
    let x = j - bc[str.charCodeAt(i + j)], y = 0;
    if(j < m - 1) {
      y = moveByGS(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
}
function moveByGS(j, m, suffix, prefix) {
  let k = m - 1 - j;
  if(suffix[k] !== -1) return j - suffix[k] + 1;
  for(let r = j + 2; r <= m - 1; r++) {
    if(prefix[m - r]) return r;
  }
  return m;
}

KMP

算法实现

//生成next数组
function generateNexts(b) {
  let k = -1,
      next = [-1];
  for(let i = 1; i < b.length; i++) {
    while(k !== -1 && b[k + 1] !== b[i]) k = next[k];
    if(b[k + 1] === b[i]) k++;
    next[i] = k;
  }
  return next;
}
function kmp(a, b) {
  let next = generateNexts(b);
  let j = 0;
  for(let i = 0; i < a.length; i++) {
    while(j > 0 && a[i] !== b[j]) j = next[j - 1] + 1;
    if(a[i] === b[j]) j++;
    if(j === b.length) return i - b.length + 1;
  }
  return -1;
}

Trie

特点：

  • 根节点不包含字符，除根节点外的每一个子节点都包含一个字符
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
  • 每个节点的所有子节点包含的字符互不相同

优点：

  • 插入效率和查询的效率很高，都为$O(m)$，其中m是字符串长度

  • 树中不同关键字不会冲突

缺点：

  • 空间消耗很大
  • 对缓存不友好
  • 当hash函数很好时，trie树的查找效率会低于哈希搜索

应用：

  • 字符串检索
  • 词频统计
  • 字符串排序
  • 前缀匹配
  • 自动输入补全

Trie的实现

/**
 * Initialize your data structure here.
 */
var Trie = function() {
    this.trie = {};
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
    var cur = this.trie;
    for (let i = 0; i < word.length; i++) {
        if (!cur[word[i]]) {
            cur[word[i]] = {
                value: i === word.length - 1
            };
            cur = cur[word[i]];
        } else {
            cur = cur[word[i]];
            if (i === word.length - 1) cur.value = true;
        }
    }
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    var cur = this.trie;
    for(let i = 0; i < word.length; i++){
        if(!cur[word[i]]){
            return false;
        }else {
            cur = cur[word[i]];
        }
    }
    return cur.value;
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    var cur = this.trie;
    for(let i = 0; i < prefix.length; i++){
        if(!cur[prefix[i]]){
            return false;
        }else {
            cur = cur[prefix[i]];
        }
    }
    return true;
};

/** 
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

 上一页

CSS

 评论