KMP算法介绍

快来打我* 2023-08-17 15:46 71阅读 0赞

## 简介 ##

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，称之为Knuth-Morris-Pratt算法，简称KMP算法。该算法与Brute-Force算法相比有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。

## 实现 ##

### 1、从模式串t中提取加速匹配的信息 ###

kmp就是通过模式串本身的特点来加速的，具体来说就是求next数组，next数组的定义如下：

$$next\[j\]=\\begin\{cases\} -1 & 当j=0时\\\\MAX\\\{k \\,|\\, 0<k<j \{\\ \} and \{\\ \} "t\_0t\_1\\cdot \\cdot \\cdot t\_\{k-1\}"="t\_\{j-k\}t\_\{j-k+1\}\\cdot \\cdot \\cdot t\_\{j-1\}"\\\}&前后缀相等时\\\\0 &其它情况\\end\{cases\}$$

next数组的求解过程如下：

1.  next\[0\]=-1（特殊值，标记），next\[1\]=0（j=1，在1~j-1的位置上没有字符，属于其它情况）
2.  如果next\[j\] = k，表示有$"t\_0t\_1\\cdot \\cdot \\cdot t\_\{k-1\}"="t\_\{j-k\}t\_\{j-k+1\}\\cdot \\cdot \\cdot t\_\{j-1\}"$：

*  若$t\_k=t\_j$，即有$"t\_0t\_1\\cdot \\cdot \\cdot t\_\{k-1\}t\_k"="t\_\{j-k\}t\_\{j-k+1\}\\cdot \\cdot \\cdot t\_\{j-1\} t\_j"$，显然有$next\[j+1\]=k+1$。
 *  若$t\_k\\neq t\_j$，说明$t\_j$之前不存在长度为$next\[j\]+1$的字串和开头字符起的字串相同，那么是否存在一个长度较短的字串和开头字符起的字串相同呢？设$\{k\}'=next\[k\]$（回退），则下一步应该将$t\_j$与$t\_\{ \{k\}'\}$比较：若$t\_j=t\_\{ \{k\}'\}$，则说明$t\_j$之前存在长度为$next\[\{k\}'\]+1$的字串和开头字符起的字串相同；否则依此类推找更短的字串。知道不存在可匹配的字串，置$next\[j+1\]=0$。所以，当$t\_k \\neq t\_j时，置$k=next\[k\]$

例如：

求模式串$t="aaaba"$的next数组。

解：

1 //char x[]是模式串
     2 void pre_kmp()
     3 {
     4     int m = strlen(x);
     5     int i = 0, j = nexts[0] = -1;
     6     while (i < m)
     7     {
     8         while (j != -1 && x[i] != x[j])  j = nexts[j];    //当前不匹配，j回退，寻找是否存在一个长度较小的字串和开头的字串相等
     9         nexts[++i] = ++j;                //j等于已匹配的长度，如果当前位置也匹配，则nexts直接为j+1
    10     }
    11 }

### 2、KMP算法的模式匹配过程 ###

简单的说就是，若当前位置匹配则模式串和主串指针同时后移一位，若当前位置不匹配，则主串指针不动，模式串指针回退到next\[i\]，如果回退的位置上仍不匹配继续回退。

大概这样：

![1365470-20190131110057264-2122534136.png][]

1 //返回x在y中出现的次数（可重叠）
     2 int KMP_Count()    //x为模式串，y为主串
     3 {
     4     int i = 0, j = 0, ans = 0;
     5     int m = strlen(x), n = strlen(y);
     6     pre_kmp();
     7     while (i < n)
     8     {
     9         while (j != -1 && y[i] != x[j])  j = nexts[j];        //当前位置不同，j回退
    10         i++; j++;                //当前位置相同，i、j同时后移一位
    11         if (j >= m)
    12         {
    13             ans++;
    14             j = nexts[j];
    15         }
    16     }
    17     return ans;
    18 }

**注：**

*  匹配时分为主串可重复和主串不可重复，两者只是在找到匹配串时模式串的回溯位置不同
 *  next数组保证了真前缀和真后缀尽可能长的匹配，这样才能保证匹配时不会出现遗漏，同时模式串也能右移的更多
 *  pre\_kmp求next数组时求了字符串最后一个字符的下一位，因为做题时经常需要这个值

## 复杂度 ##

一般化结论： 
    - 一个周期内的比较次数：1 * (M - 1) + M 
    - 周期长度：M 
    - 周期个数：N/M 
    - 比较总次数： 周期个数 * 一个周期内额比较次数 = (2 - 1/M)*N < 2N

所以最坏情况下模式串中每个字符的平均比较次数小于2，所以比较部分的平均时间复杂度为O(N)。

求next数组的过程其实主串与主串比较（KMP是将主串与模式串匹配），所以时间复杂度为O(M)。

总的时间复杂度为O(M+N)。

参考链接：

*  [KMP时间复杂度分析][KMP]
 *  [KMP的时间复杂度是如何计算的？][KMP 1]

转载于:https://www.cnblogs.com/lfri/p/10339410.html

[1365470-20190131110057264-2122534136.png]: /images/20230810/67e51b404eea4fbd9f564b2a8912b65e.png
[KMP]: https://blog.csdn.net/niukai1768/article/details/79579709
[KMP 1]: https://segmentfault.com/q/1010000014560162