KMP算法(javascript实现)

KMP算法是很经典的字符串匹配算法，主要通过部分匹配表来提高匹配效率。
具体的算法步骤可以看文章这里。下面附javascript的实现代码。

1.首先需要对待搜索字符串生成部分匹配表，代码如下。

function createPartialMatch(search) {
  let map = {};
  for (let i = 0; i < search.length; i++) {
    if (i === 0) {
      map[i] = 0;
    } else {
      let str = search.substr(0, i + 1);
      for (let j = 0; j < i; j++) {
        // 获取前缀
        let beforestr = str.substr(0, j + 1);
        // 获取后缀
        let afterstr = str.substr(-j - 1);
        if (beforestr === afterstr) {
          map[i] = beforestr.length;
        }
        if (!map[i]) {
          map[i] = 0;
        }
      }
    }
  }
  return map;
}

2.依次比较，首位不匹配则进一位，否则移动位数等于已匹配的字符数减去上面得到的部分匹配值，代码如下。

function match(str, search) {
  let map = createPartialMatch(search);
  let i1 = 0,
    i2 = 0;
  let l1 = str.length,
    l2 = search.length;
  while (i1 <= l1 - l2) {
    let j = 0;
    for (i2 = 0; i2 < l2; i2++) {
      if (search[i2] === str[i1]) {
        j++;
        i1++;
        if (j === l2) {
          return [i1 - l2, i1];
        }
      } else {
        //移动位数 = 已匹配的字符数 - 对应的部分匹配值
        //至少移动一位
        i1 += j - map[i2 - 1] || 1;
        break;
      }
    }
  }
}