跳转至

KMP

KMP 算法是一种字符串匹配算法,可以在 \(O(n+m)\) 的时间复杂度内实现两个字符串的匹配。这个算法由高德纳沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。Knuth-Morris-Pratt (简称为KMP算法

  • 尽可能利用残余的信息,是KMP算法的思想所在;
  • 如果把模式串视为一把标尺,在主串上移动,Brute-Force 就是每次失配之后只右移一位;KMP 算法则是每次失配之后,移很多位,跳过那些不可能匹配成功的位置。

前缀函数

KMP 算法是对前缀函数的一种应用。对前缀函数的定义:

给定一个长度为 \(n\) 的字符串 \(s\),其 前缀函数 被定义为一个长度为 \(n\) 的数组 \(\pi\)。 其中 \(\pi[i]\) 的定义是:

  1. 如果子串 \(s[0\dots i]\) 有一对相等的真前缀与真后缀:\(s[0\dots k-1]\)\(s[i - (k - 1) \dots i]\),那么 \(\pi[i]\) 就是这个相等的真前缀(或者真后缀,因为它们相等:))的长度,也就是 \(\pi[i]=k\)
  2. 如果不止有一对相等的,那么 \(\pi[i]\) 就是其中最长的那一对的长度;
  3. 如果没有相等的,那么 \(\pi[i]=0\)

简单来说 \(\pi[i]\) 就是,子串 \(s[0\dots i]\) 最长的相等的真前缀与真后缀的长度。

用数学语言描述如下:

\[ \pi[i] = \max_{k = 0 \dots i}\{k: s[0 \dots k - 1] = s[i - (k - 1) \dots i]\} \]

特别地,规定 \(\pi[0]=0\)

朴素的暴力运算实现
  1. 在一个循环中以 \(i = 1\to n - 1\) 的顺序计算前缀函数 \(\pi[i]\) 的值(\(\pi[0]\) 被赋值为 \(0\));
  2. 为了计算当前的前缀函数值 \(\pi[i]\),我们令变量 \(j\) 从最大的真前缀长度 \(i\) 开始尝试;
  3. 如果当前长度下真前缀和真后缀相等,则此时长度为 \(\pi[i]\),否则令 j 自减 1,继续匹配,直到 \(j=0\)
  4. 如果 \(j = 0\) 并且仍没有任何一次匹配,则置 \(\pi[i] = 0\) 并移至下一个下标 \(i + 1\)
vector<int> prefix_function(string s) {
  int n = s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    for (int j = i; j >= 0; j--) {
      // j 为前后缀的长度,从大到小尝试
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
    }
  }
  return pi;
}
使用动态规划优化的实现

优化的要点:

  • 相邻的前缀函数值至多增加 1(在最好的情况下增加 1);
  • 下一个前缀函数值要么增加 1,要么维持不变,要么减少;

前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org) KMP算法 - 维基百科,自由的百科全书 (wikipedia.org) The Knuth-Morris-Pratt Algorithm in my own words - jBoxer (jakeboxer.com)