假設(shè)給定兩個字符串 F 和 S，怎么求 S 在 F 中出現(xiàn)的第一個位置？細(xì)想一下就能知道其實(shí)就是 JS 中 String 的實(shí)例方法 indexOf()的實(shí)現(xiàn)，像下面這樣：

const father = "I AM YOUR FATHER";
const son = "YOUR FATHER ARE MY GRANDPA";
console.log(father.indexOf(son)); // 5

不過我們當(dāng)然不能就直接使用indexOf，那就不叫算法了。本文將從最簡單的解法開始，再講解 KMP 算法的原理。

直接解法

也可以叫暴力解法，就是遍歷母串，和子串一一匹配，直到子串全部匹配完畢，如果中間有匹配不上的情況，就把母串從上一次開始匹配的位置后移一位，子串從 0 開始匹配，重復(fù)這個過程，直到匹配上或者匹配不上。代碼如下：

const strStr = function(f, s) {
  // s為空，直接返回
  if (s === "") {
    return 0;
  }
  let i = 0;
  let j = 0;
  while (i < f.length) {
    // 如果匹配，各自加一，繼續(xù)匹配
    if (f.charAt(i) === s.charAt(j)) {
      i++;
      j++;
    } else {
      // 如果不匹配，i置為上一輪匹配的下一位，j置為0
      i = i - j + 1;
      j = 0;
    }
    // 全部匹配上，返回
    if (j === s.length) {
      return i - j;
    }
  }
  return -1;
};

按說上面的解法對咱來說已經(jīng)滿足需要了，但是有三位大佬看了這種解法說，垃圾，這也叫算法？于是，我們有了 KMP 算法。

KMP

什么叫 kmp？就是提出這種算法的三個人的名字的首字母縮寫，我們要搞懂的是名字后面的解法。

上面的直接解法是粗暴的一一匹配，效率較低，kmp 三人發(fā)現(xiàn)可以利用匹配失敗時(shí)某種信息減少匹配的次數(shù)，從而提升效率，這個信息就是這個算法的關(guān)鍵點(diǎn)。
是什么信息呢？簡單說就是子串在匹配失敗位置之前的字符串的最大相同的前綴后綴的長度。比較拗口，斷句來看就是，子串在匹配失敗位置，之前的字符串的，最大相同的前綴后綴，的長度。

關(guān)鍵點(diǎn)在最大相同的前綴后綴，什么叫最大相同的前綴后綴？
比如ABCDAB，最大相同前后綴是AB，長度是 2，
比如123123，最大相同前后綴是123，長度是 3。

我們需要的就是這個長度，我們來看一下這個長度有什么用。

我們假設(shè)以下兩個字符串：

const m = "ABCDAB ABCDABCDABD";
const p = "ABCDABD";

可以想到，當(dāng)匹配到 m[6]、p[6]時(shí)，我們能獲取到的信息是前六位匹配，前六位的最大相同前后綴長度是AB，長度為 2。當(dāng)不匹配時(shí)，暴力解法的做法是將母串后移一位，子串從 0 開始重新匹配，我們先模擬一下這個過程：

1. 當(dāng)匹配到 m[6] p[6]時(shí)不匹配，m 后移一位從 m[1]開始，p 從 p[0]開始
2. m[1]和 p[0]不匹配，繼續(xù)移位
3. m[2]和 p[0]不匹配，繼續(xù)移位
4. 一直到 m[4]和 p[0]，終于匹配上了 A，然后下一位的 B 也能匹配上，直到 m[6]，p[2]

而匹配上的這倆正好是我們的最大相同前后綴，相比從第 6 位沒匹配上開始，m 位置沒變，還是 6，p 從 6 移到了 2，這個 2 正好是上面最大相同前后綴的長度(緣分啊)，所以這個長度的作用就是當(dāng)匹配不到時(shí)，子串回退到的索引。我們給存儲子串每位最大相同前后綴長度的數(shù)組取名為 next，每次匹配不到時(shí)子串索引置為相應(yīng)值即可。

那么這個 next 數(shù)組該怎么求呢？我們默認(rèn)將第一位置為-1，因?yàn)榈谝晃粵]匹配上也不能再向左移動了，代碼如下：

const getNext = str => {
  let j = 0;
  let k = -1;
  const next = [-1];
  while (j < str.length - 1) {
    if (k === -1 || str[j] === str[k]) {
      j++;
      k++;
      next[j] = k;
    } else {
      k = next[k];
    }
  }
  return next;
};

所以結(jié)合上面這個方法，我們有:

const strStr = function(f, s) {
  // s為空，直接返回
  if (s === "") {
    return 0;
  }
  const next = getNext(s);
  let i = 0;
  let j = 0;
  while (i < f.length) {
    // 如果匹配，各自加一，繼續(xù)匹配
    if (j === -1 || f.charAt(i) === s.charAt(j)) {
      i++;
      j++;
    } else {
      // 如果不匹配，i不用改變，j置為此位置最大前后綴的長度
      j = next[j];
    }
    // 全部匹配上，返回
    if (j === s.length) {
      return i - j;
    }
  }
  return -1;
};

上面便是 kmp 的解法，然鵝，還可以再優(yōu)化，看以下例子：

example1.png

當(dāng)匹配不到時(shí)，下一步我們移動的位置應(yīng)該是這樣

example2.png

可以發(fā)現(xiàn)，這步匹配是完全沒意義的，因?yàn)樯弦徊降?B 已經(jīng)不匹配，這步的 B 肯定也不匹配了。發(fā)生問題的原因在于
p[j] == p[next[j]]，移動到的值正好等于現(xiàn)在的，這步移動就可以省略掉，進(jìn)一步提升效率。我們修改一下求 next 數(shù)組的方法，如下：

const getNext = str => {
  let j = 0;
  let k = -1;
  const next = [-1];
  while (j < str.length - 1) {
    if (k === -1 || str[j] === str[k]) {
      j++;
      k++;
      if (p[j] !== p[k]) {
        next[j] = k;
      } else {
        next[j] = next[k];
      }
    } else {
      k = next[k];
    }
  }
  return next;
};

OK，以上便是 kmp 解法的講解，我主要是用推導(dǎo)的方式，發(fā)現(xiàn)規(guī)律，里面其實(shí)是有數(shù)學(xué)公式佐證的，但是比較不好理解，就不貼出來了，有問題歡迎交流。

參考：

1. 這里
2. 這里