KMP算法学习笔记

· · 算法·理论

KMP算法学习笔记

KMP 算法简述

KMP 算法名字的由来

KMP 算法是对字符串匹配算法的一种简化，其同时由 D.E.Knuth J.H.Morris 和 V.R.Pratt 发现，所以被简称为 KMP 算法。

KMP 算法的用处

KMP 算法可以以 O(m + n) 的时间复杂度进行字符串匹配。

“字符串 A 是否为字符串 B 的子串？如果是的话出现在 B 的哪些位置？”该问题就是字符串匹配问题，字符串 A 被称为模式串，字符串 B 被称为主串。

——在这里，我们把模式串称为 p，文本串（也就是主串）称为 t。

Brute-Force 算法

Brute-Force 算法图片 

ababc|abc
i----|j--
-i---|-j-
--i--|--j
-i---|j--
--i--|j--
---i-|-j-
----i|--j
---i-|j--
----i|j--
-----|j--
i 出界，程序结束

如图，当 p_j=t_i 时，i\gets i+1，j\gets j+1；当 p_j\ne t_i 时，i\gets i-j+1 ，j\gets 0，循环往复，直至匹配完成（匹配完成时，i\gets i-j+1，j\gets 0）。
问题来了：我们能不能利用以往的信息，让 i 不回退也能进行匹配呢？
答案是：能！

next 数组

next 数组的定义

对于模式串 p，我们定义一个数组 next 表示模式串前缀的真前缀和真后缀最大相同的位置，使得对于任意 next_j，有 next_j=\max\{0,k|p_0\sim p_{k-1} = p_{j-k+1}\sim p_j \}(k\le j)。

next 数组的用法

比如我们考虑一组样例：

p:abcab-------
t:abcacababcab

首先，前四位按位匹配成功，遇到第五位不同，而这时，我们选择将abcad向右移三位，或者可以直接理解为移动到模式串中与失配字符相同的那一位。可以简单地理解为，我们将两个已经遍历过的模式串字符重合，导致我们可以不用一位一位地移动，而是根据相同的字符来实现快速移动。

p:---abcde----
t:abcacababcab

（这里加上 -，方便读者阅读）
对于模式串 abcab，其 next_4 为 1（abca），表示其已经匹配的四位中前面第一位和倒数第一位相等，我们应将前面的 a 移动至后面的 a 所占的位置，而它们相距 4-1=3 位。（也就是指针 i 不动，指针 j 往前移 3 位）

但有时不光只会有单个字符重复：

p:abcabc--------
t:abcabdababcabc

当我们发现在第六位失配时，我们可以将模式串的第一二位移动到第四五位，因为它们相同 qwq .

p:---abcabc-----
t:abcabdababcabc

（这里忠于原文，不做其他改动）
对于模式串 abcabc，其 next_5 为 2（abcab），表示其已经匹配的五位中前面两位和倒数两位相等，我们应将前面的 ab 移动至后面的 ab 所占的位置，而它们相距 5-2=3 位。（也就是指针 i 不动，指针 j 往前移 3 位）

next 数组的求法

暴力算法

先枚举每个 i，再枚举 next_i 的所有可能值，最后比较字符串，复杂度为 O(n^3)。

优化

\therefore next_0=0 \because next_{i}=\max\{0,k|p_0\sim p_{k-1} = p_{i-k+1}\sim p_{i} \}(k\le i),p_0\sim p_{next_{i-1}-1} = p_{i-next_{i-1}+1}\sim p_i \therefore p_{i}=p_{next_{i-1}}\Leftrightarrow next_{i}= next_{i-1}+1

举个栗子： 

0123
---i
abab
\because next_2=1,p_3=p_{next_2} \therefore next_3=next_{2}+1=1+1=2

问题来了，p_{i}\ne p_{next_{i-1}} 时我们怎么办？

\because next_{i}=\max\{0,k|p_0\sim p_{k-1} = p_{i-k+1}\sim p_{i} \}(k\le i) \therefore p_{0}\sim p_{k-1}=p_{i-k}\sim p_{i-1}\land p_k=p_i\Rightarrow next_i=k+1

举个例子：

0123456
abaabab
------i
\because next_5=3 \therefore p_0\sim p_2=p_3\sim p_5 \therefore p_2=p_5 \because next_2=1 \therefore p_0=p_2 \therefore p_5=p_0 \because p_6=p_1 \therefore next_6=2

若 p_6=\text{c}，则 p_6\ne p_1，再检测得 p_6\ne p_0，最后得 next_6=0。

最终代码：

void makeNext(char s[],int next[])
{
   int len = strlen(s);
   next[0]=0;                    //初始化
   for(int i=1,k=0;i<len;i++)
   {
       while(k>0 && s[k]!=s[i])  //这个while是最关键的部分
           k=next[k-1]; 
           //等价于  k=next[next[i-1]-1]
           //等号右边的k起的只是下标的作用
       if(s[k]==s[i])            
           k++;                  //相等就+1
       next[i]=k;                //赋值
   }
}

复杂度：O(m+n)

解释：对于任意 k ，因为 k=next_{next_{next_{...next_{i-1}...}-1}-1}，所以 p_{0}\sim p_{k-1}=p_{i-k}\sim p_{i-1}，p_k=p_i\Rightarrow next_i=k。

参考文献 (划掉)