kmp算法(JS版)

KMP

KMP是一种高效的字符串匹配算法，用来在主字符串中查找模式字符串的位置

比如在“hello,world”主串中查找“world”模式串的位置)。

核心思想

在失配时, 将模板字符串失配字符的下标退回到前面相应位置 ，这样就可以跳过大多数的失配步骤。而每次p串移动的步数就是通过查找next[ ]数组确定的。比如 :

父亲字符串 : aabaabaaf

模板字符串 : aabaaf

当模板字符串的f不匹配父字符串的b 时, 模板字符串中字符f 对应的下标j就会退回到包括前5个字符组成的子串的最长相同前后缀的长度, 也就是2, 于是退回到下标为2的位置, 从模板字符串的b字符继续开始和父字符串进行匹配, 至始至终父字符串的匹配下标都未移动哦~

KMP 主要分两步：

1. 求next数组
2. 匹配字符串

举例 + 详解

详解 : 都在注释中了

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
const num = 4;
const rows = [];
rl.on('line', function(data){
  rows.push(data);
  if (rows.length == num) {
    const res = [];
    const n = Number(rows[0]);
    const m = Number(rows[2]);
    const p = rows[1];
    const s = rows[3];
    // 初始化next数组为0, 单个数字是没有前后缀的, 也没有长度
    const next = [0]
    // 求next数组 : next[i]就是包括i之前这个子串最长相等前后缀的长度
    // j代表前缀的末尾位置, 前缀从下标0开始, i代表后缀的末尾位置, 后缀是从下标1开始, 因为单个数字是没有前后缀的
    for(let i = 1, j = 0; i < n; i++) {
 // 关于 j > 0 : 因为下标为0时j无法回退到前一个数字的next值, 也就是数组下标-1也有问题, 所以要进行判定
 // 关于 while : 因为j的回退也是需要持续进行的, 直到前后缀一致或者j回退到下标为0的位置, 这个地方也是易错点
 // 关于 j = next[j - 1] : 当不匹配时, j要回退到前一个数字的next值的位置, 也就是包括i在内的字符串的最长相同前后缀的长度
      while(j && p[i] != p[j]) j = next[j - 1];
      // 当匹配时, j++, 因为j不仅代表前缀末尾的位置, 也代表着包括i之前这个子串的最长相等前后缀的长度, 此时匹配了肯定要加一
      if(p[i] === p[j])j++; 
      // 因为j代表着包括i之前这个子串的最长相等前后缀的长度, 也就是我们要求的next[i]的值, 最后赋值即可
      next[i] = j;
    }
    // 进行匹配
    // 都从第一个数开始匹配, 所以下标都从0开始, i为父字符串下标, j为模板字符串下标
  for (let i = 0, j = 0; i < m; i++) {
  // 当j为0时, 无需回退且数组也会越界
  // while的作用: 由于移动后可能仍然失配, 所以目的是要保持匹配
  // 当不匹配时, j回退到前一个数字的next值的位置, 继续下一步匹配, 注意这时候i是不变的, 也就是说i一直向后, 只有j是不断回退
      while (j && s[i] != p[j]) j = next[j - 1]; 
      // 当匹配成功时, j++
      if (s[i] == p[j]) j++;
      // 如果模板字符串已全匹配完, 则匹配完成
      if (j == n) {
        res.push(i - n + 1);
        j = next[j - 1];
      }
      // 如果未匹配完成, 则i++, 继续下一个字符的匹配
    }
    console.log(res.join(' '));
    rl.close();
  }
})

over

例子2 + 无注释版

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    let next = [0];
    for(let j = 0, i = 1; i < needle.length; i++) {
        while(j && needle[i] != needle[j]) j = next[j - 1];
        if(needle[i] === needle[j]) j++;
        next[i] = j;
    }
    for(let i = 0, j = 0; i < haystack.length; i++) {
        while(j && needle[j] !== haystack[i]) j = next[j - 1];
        if(needle[j] === haystack[i]) j++;
        if(j === needle.length) {
            return i - j + 1;
        }
    }
    return -1;
};