KMP算法JS实现

参考阮一峰的《字符串匹配的KMP算法》，用JS实现一版，备忘~

// 主串
let str1 = 'BBC ABCDAB ABCDABCDABDEDC';
// 模式串
let str2 = 'ABCDABD';

/**
 * 算出《部分匹配表》Partial Match Table
 * 参考文档：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
 * @method
 * @param  {String} str 要计算的字符串
 * @return {Array}     部分匹配表
 */
let getPMT = (str = '') => {
  if(str.length === 0)return [];
  let pmt = [0];
  let k = 2;
  while(k <= str.length){
    let temp = str.substring(0, k);
    let length = temp.length;
    // 前缀
    let prefix = temp.substring(0, length - 1).split('').map((item, index) => {
      return temp.substring(0, index + 1);
    });
    // 后缀
    let suffix = temp.substring(1).split('').map((item, index) => {
      return temp.substring(index + 1);
    });
    let publicLength = 0;
    // 比较前缀后缀得出最长公共字符长度
    prefix.forEach(preitem => {
      suffix.forEach(sufitem => {
        if(preitem === sufitem){
          publicLength = preitem.length > publicLength ? preitem.length : publicLength;
        }
      })    
    })
    pmt.push(publicLength);
    k++;
  }
  return pmt;
}

let pmt = getPMT(str2);
let m = 0;
let n = 0;

while(m < str1.length && n < str2.length){
  if(str1[m] === str2[n]){ // 匹配时，继续比较下一个字符
    n++;
    m++;
  }else if(n > 0){ // 当前不匹配时，如果前面已匹配字符数 > 0，模式串索引往前移动pmt[n - 1]位
    n = pmt[n - 1];
  }else{
    m++;
  }
}
if(n === str2.length){
  console.log(`str1包含str2，索引位置为${m - str2.length}至${m - 1}`);
}else{
  console.log('str1不包含str2');
}