跳到主要内容

认识KMP算法

介绍​

Knuth–Morris–Pratt（KMP）算法是一种改进的字符串匹配算法，它的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是 O(m+n)。

原理​

有一个文本串为: aabaabaaf

有一个模式串为: aabaaf

现在要看文本串中是否能够匹配到模式串，那么文本串是怎么匹配模式串的呢？

一、确定最长公共前缀后缀数组​

模式串为 aabaaf , 最长公共前缀后缀数组为:

  • 如果字符串为 a
前缀为  没有前缀(不包含尾字符)

后缀为  没有后缀(不包含首字符)

即最长公共前缀后缀 没有，长度为 0
  • 如果字符串为 aa
前缀为  a(不包含尾字符)

后缀为  a(不包含首字符)

前缀和后缀中有一个相同的 a ，即最长公共前缀后缀长度为 1
  • 如果字符串为 aab
前缀为  a aa(不包含尾字符)

后缀为  ab(不包含首字符)

前缀和后缀中没有相同的字符串，即最长公共前缀后缀长度为 0
  • 如果字符串为 aaba
前缀为  a aa aab(不包含尾字符)

后缀为  a ba aba(不包含首字符)

前缀和后缀中有一个相同的字符串，即最长公共前缀后缀长度为 1
  • 如果字符串为 aabaa
前缀为  a aa aab aaba(不包含尾字符)

后缀为  a aa baa abaa(不包含首字符)

前缀和后缀中有两个个相同的字符串，即最长公共前缀后缀长度为 2
  • 如果字符串为 aabaaf
前缀为 a aa aab aaba aabaa (不包含尾字符)

后缀为 f af aaf baaf abaaf (不包含首字符)
前缀和后缀中没有相同的字符串，即最长公共前缀后缀长度为 0

所以该模式串最长公共前缀后缀数组为 [0,1,0,1,2,0]

通过第一步，确定了以下关系:

模式串: a a b a a f

前缀表: 0 1 0 1 2 0

二、确定不匹配字符,确定下一步应该重新开始的下标​

文本串: a a b a a b a a f

模式串: a a b a a f

前缀表: 0 1 0 1 2 0

  1. 当文本串匹配到 b 时，此时模式串为 f ，发现不匹配。此时要找不匹配字符 f 的前一位字符所对应的前缀表数值（思想:遇见冲突，向前回退）
  2. f 的前一位字符 a 对应的前缀表数值为 2, 所以下一步应该重新开始的下标为 aabaa 中的 2 的位置，即从 b 开始继续匹配

实现​

构造 next 数组​

next 数组即为一个字符串的最长公共前缀后缀数组

思路:

  • 初始化
    • i : 指向后缀末尾位置（始终不包括第一个字符，所以从 1 开始）
    • j : 指向前缀末尾位置、也代表着最长公共前缀后缀长度
  • 前后缀相同，即 s[i]==s[j] 时 : j 往后移即可(同时也代表着 s[i] 字符的最长公共前缀后缀长度+1)
  • 前后缀不相同，即 s[i]!=s[j] 时 : j 要取 j 前一个字符所对应的最长公共前缀后缀长度 即 next[j-1]
  • 更新 next 值

:::details 点击查看代码

function getNext(s){
  let j=0;
  let next=[j];
  for(let i=1;i<s.length;i++){
    while(j>0&&s[i]!=s[j]){
      j=next[j-1];
    }
    if(s[i]==s[j]){
      j++
    }
    next[i]=j;
  }
  return next
}

:::