KMP算法完美图解

爱被打了一巴掌 2022-06-06 22:42 208阅读 0赞

讲这个算法之前，我们首先了解几个概念：

**串：**又称字符串，是由零个或多个字符组成的有限序列。如*S*="abcdef"

> **子串：**串中任意个连续的字符组成的子序列，称为该串的子串，原串称为子串的主串。如*T*="cde"，*T*是*S*的子串。子串在主串中的位置，用子串的第一个字符在主串中出现的位置表示。*T*在*S*中的位置为3。

![Center][]

> **模式匹配：**子串的定位运算称为串的模式匹配或串匹配。
> 
> 假设有两个串*S*，*T*，设*S*为主串，也称正文串，*T*为子串，也称为模式，在主串*S*中查找与模式*T*相匹配的子串，如果查找成功，返回匹配的子串第一个字符在主串中的位置。
> 
> 最笨的办法就是穷举所有*S*的所有子串，判断是否与*T*匹配。
> 
> 例如：*S*="abaabaabeca"，*T*=" abaabe"，求子串*T*在主串*S*中的位置。

1.  从 *S*串第1个字符开始： *i*=1， *j*=1，比较两个字符是否相等，如果相等，则 *i*\++， *j*\++；如果不等则执行第2步；
    
    ![Center 1][]
2.  从 *S*串第2个字符开始：即 *i*退回到 *i*\- *j*\+2的位置，即 *i*=2， *j*=1，比较两个字符是否相等，如果相等，则 *i*\++， *j*\++；如果不等则执行第3步；
    
    ![Center 2][]
3.  从 *S*串第3个字符开始：即 *i*退回到 *i*\- *j*\+2的位置，即 *i*=3， *j*=1，比较两个字符是否相等，如果相等，则 *i*\++， *j*\++；如果不等则执行第4步；
    
    ![Center 3][]
4.  从 *S*串第4个字符开始：即 *i*退回到 *i*\- *j*\+2的位置，即 *i*=4， *j*=1，比较两个字符是否相等，如果相等，则 *i*\++， *j*\++；此时 *T*串比较完了，执行第5步；
    
    ![Center 4][]
5.  需要返回子串在主串 *S*中第一个字符出现的位置，即 *i*\- *m*=10-6=4， *m*为 *T*串的长度。

> 上述算法称为BF(Brute Force)算法，Brute Force的意思是蛮力，暴力穷举。其时间复杂度最坏达到*O*(*n*\**m*)，*n*，*m*分别为*S、T*串的长度。
> 
> 实际上，完全没必要从*S*的每一个字符开始，暴力穷举每一种情况，Knuth、Morris和Pratt对该算法进行了改进，称为KMP算法。
> 
> 我们再回头看刚才的例子：
> 
> 从*S*串第1个字符开始：*i*=1，*j*=1，比较两个字符是否相等，如果相等，则*i*\++，*j*\++；按照BP算法，如果不等则*i*退回到*i*\-*j*\+2的位置，即*i*=2，*j*=1。

![Center 5][]

> 其实*i*不用回退，让*j*回退到第3个位置，接着比较即可。

![Center 6][]

> 是不是像*T*串向右滑动了一段距离？
> 
> 为什么可以这样？为什么让*j*回退到第3个位置？而不是第2个？第四个？
> 
> 因为*T*串中开头的两个字符和*i*指向的字符前面的两个字符一模一样噢，那*j*就可以回退到第3个位置继续比较了，因为前面两个字符已经相等了。

![Center 7][]

> 那我们怎么知道*T*串中开头的两个字符和*i*指向的字符前面的两个字符一模一样？难道还要比较？我们发现*i*指向的字符前面的两个字符和*T*串中*j*指向的字符前面两个字符一模一样，因为它们一直相等，才会*i*\++，*j*\++走到后面的位置。

![Center 8][]

> 也就是说，我们不必判断*T*串中开头的两个字母和*i*指向的字符前面的两个字符是否一样，只需要在*T*串本身比较就可以了。即*T′*的前缀和*T′*的后缀比较即可：

![Center 9][]

> 判断*T′*="*abaab*"的前缀和后缀是否相等，找相等前缀后缀的最大长度。
> 
> 长度为1的：前缀"*a*"，后缀："*b*"，不等×
> 
> 长度为2的：前缀"*ab*"，后缀："*ab*"，相等√
> 
> 长度为3的：前缀"*aba*"，后缀：" *aab*"，不等×
> 
> 长度为4的：前缀"*abaa*"，后缀："*baab*"，不等×
> 
> **注意：**前缀和后缀不可以取字符串本身。串的长度为5，前缀和后缀长度最多达到4。
> 
> 相等前缀后缀的最大长度为*l*=2，则*j*就可以回退到第*l*\+1=3个位置继续比较了。
> 
> 现在我们可以写出通用公式，*next*\[*j*\]表示*j*可以回退的位置，*T′*="*t*1*t*2…*tj*\-1"，则：

![Center 10][]

> 那么我们很容易求出*T*="*abaabe*"的*next*\[\]数组：

![Center 11][]

解释：

>  *j*=1：根据公式*next*\[1\]=0；
> 
>  *j*=2：*T′*="*a*"，没有前缀和后缀，*next*\[2\]=1；
> 
>  *j*=3：*T′*="*ab*"，前缀为"*a*"，后缀为"*b*"，不等，*next*\[3\]=1；
> 
>  *j*=4：*T′*="*aba*"，前缀为"*a*"，后缀为"*a*"，相等且*l*=1；前缀为"*ab*"，后缀为"*ba*"，不等，*next*\[4\]=*l*\+1=2；

*j*=5：*T′*="*abaa*"，前缀为"*a*"，后缀为"*a*"，相等且*l*=1；前缀为"*ab*"，后缀为"*aa*"，不等；前缀为"*aba*"，后缀为"*baa*"，不等，因此*next*\[5\]=*l*\+1=2；

*j*=6：*T′*="*abaab*"，前缀为"*a*"，后缀为"*b*"，不等；前缀为"*ab*"，后缀为"*ab*"，相等且*l*=2；前缀为"*aba*"，后缀为"*aab*"，不等；前缀为"*abaa*"，后缀为"*baab*"，不等，取最大长度2，因此*next*\[6\]=*l*\+1=3。

**这样找所有的前缀和后缀比较，是不是也是暴力穷举？**

**那怎么办呢？Look……**

用动态规划递推一下：

首先大胆假设，我们已经知道了*next*\[*j*\]=*k*，即：

![Center 12][]

那么*next*\[*j*\+1\]=?

考察以下两种情况：

1.  *tk*= *tj*：那么 *next*\[ *j*\+1\]= *k*\+1，即相等前缀和后缀的长度比 *next*\[ *j*\]多1。
    
    ![Center 13][]
2.  *tk*≠ *tj*：当两者不相等时，我们又开始了这两个串的模式匹配，找 *next*\[ *k*\]的位置 *tk*′与 *tj*比较，程序中的处理，只需要把 *next*\[ *k*\]赋值给 *k*，即 *k←next*\[ *k*\]，然后再比较 *tk*与 *tj*是否相等，如果相等则 *next*\[ *j*\+1\]= *k*\+1；

![Center 14][]

如果不相等，则继续向前找*next*\[*k*′\]，如果不相等，继续向前找，直到找到*next*\[1\]=0，停止，此时*next*\[*j*\+1\]=0+1=1，即从第一个字符开始。

![Center 15][]

求解*next*\[\]的代码实现如下：

void get_next(SString T,int next[]){ //求模式串T的next函数值
        int j=1,k=0;
        next[1]=0;
        while(j<T[0]) // T[0]为模式串T的长度
            if(k==0||T[j]==T[k])
                next[++j]=++k;
            else
                k=next[k];
    }

> 用上述方法再次求解求出*T*="*abaabe*"的*next*\[\]数组：

![Center 16][]

> 解释：

1. 初始化时**next\[1\]=0**，j=1，k=0，进入循环，判断满足k==0，则执行next\[++j\]=++k，即**next\[2\]=1**，此时**j=2，k=1**；

2. 进入循环，判断满足T\[j\]==T\[k\]，T\[2\]≠T\[1\]，则执行k=next\[k\]，即k=next\[1\]=0，此时**j=2，k=0**；

3. 进入循环，判断满足k==0，则执行next\[++j\]=++k，即**next\[3\]=1**，此时**j=3，k=1**；

4. 进入循环，判断满足T\[j\]==T\[k\]，T\[3\]=T\[1\]，则执行next\[++j\]=++k，即**next\[4\]=2**，此时**j=4，k=2**；

5. 进入循环，判断满足T\[j\]==T\[k\]，T\[4\]≠T\[2\]，则执行k=next\[k\]，即k=next\[2\]=1，此时**j=4，k=1**；

6. 进入循环，判断满足T\[j\]==T\[k\]，T\[4\]=T\[1\]，则执行next\[++j\]=++k，即**next\[5\]=2**，此时**j=5，k=2**；

7. 进入循环，判断满足T\[j\]==T\[k\]，T\[5\]=T\[2\]，则执行next\[++j\]=++k，即**next\[6\]=3**，此时**j=6，k=3**；

8. j=T\[0\]，循环结束。

> 结果是不是和穷举前缀后缀一模一样？
> 
> 有了next\[\]数组，就很容易进行模式匹配了，当S\[i\]≠T\[j\]时，j退回到next\[j\]的位置继续比较即可。
> 
> 这样求解非常方便，迅速，但是也发现有一个**问题**：当S\[i\]≠T\[j\]时，j退回到next\[j\]，然后S\[i\]与T\[k\]比较。这样的确没错，但是如果T\[k\]=T\[j\]，这次比较就没必要了，因为我们刚知道S\[i\]≠T\[j\]啊，那么肯定S\[i\]≠T\[k\]，完全没必要再比了。

![Center 17][]

> 再向前找下一个next\[\]，即找next\[k\]的位置，继续比较就可以了。本来应该和第k个位置比较呢，相当于跳到了k的下一个位置。减少了一次无效比较。

![Center 18][]

修改程序：

求解*next*\[\]的**改进**代码实现如下：

void get_next2(SString T, int next[]){ //求模式串T的next函数值
        int j=1,k=0;
        next[1]=0;
        while(j<T[0]){  // T[0]模式串T的长度   
            if(k==0||T[j]==T[k]){
                j++;
                k++;
                if(T[j]==T[k])
                    next[j]=next[k]; //调到k的下一个位置，即next[k]
                else
                    next[j]=k;
            }
            else
                k=next[k];
       }
    }

**完美～～～**

/\*\*\*KMP及改进算法\*\*\*/

#include<iostream>/***KMP算法***/
    #include<cstring>
    using namespace std;
    #define Maxsize 100
    typedef char SString[Maxsize+1];//0号单元存放串的长度
    
    bool StrAssign(SString &T,char *chars){//生成一个其值等于chars的串T
    	int i;
    	if(strlen(chars)>Maxsize)
    		return false;
    	else{
    		T[0]=strlen(chars);
    		for(i=1;i<=T[0];i++){
                T[i]=*(chars+i-1);
                cout<<T[i]<<"  ";
            }
            cout<<endl;
    		return true;
    	}
    }
    
    int Index_BF(SString S,SString T,int pos){//BF算法
     	// 求T在主串S中第pos个字符之后第一次出现的位置
    	//其中，T非空，1≤pos≤s[0],s[0]存放S串的长度
    	int i=pos,j=1,sum=0;
    	while(i<=S[0]&&j<=T[0]){
            sum++;
            if(S[i]==T[j]){//如果相等，则继续比较后面的字符
    			i++;
    			j++;
    		}
    		else{
    			i=i-j+2; //i退回到上一轮开始比较的下一个字符
    			j=1;  //j退回到第1个字符
    		}
        }
    	cout<<"一共比较了"<<sum<<"次"<<endl;
    	if(j>T[0]) // 匹配成功
    		return i-T[0];
    	else
    		return 0;
    }
    
    void get_next(SString T,int next[]){//计算next函数值
    	int j=1,k=0;
    	next[1]=0;
    	while(j<T[0]){
    	    if(k==0||T[j]==T[k])
                next[++j]=++k;
    		else
    			k=next[k];
    	}
        cout<<"-----next[]-------"<<endl;
        for(j=1;j<=T[0];j++)
            cout<<next[j]<<"  ";
        cout<<endl;
    }
    
    void get_next2(SString T,int next[]){//计算next函数值改进算法
    	int j=1,k=0;
    	next[1]=0;
    	while(j<T[0]){
    	    if(k==0||T[j]==T[k]){
                j++;
                k++;
                if(T[j]==T[k])
                    next[j]=next[k];
                else
                    next[j]=k;
            }
    		else
    			k=next[k];
    	}
        cout<<"-----next[]-------"<<endl;
        for(j=1;j<=T[0];j++)
            cout<<next[j]<<"  ";
        cout<<endl;
    }
    
    int Index_KMP(SString S,SString T,int pos,int next[]){//KMP算法
    	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
    	//其中，T非空，1≤pos≤StrLength(S)
    	int i=pos,j=1,sum=0;
    	while(i<=S[0]&&j<=T[0]){
            sum++;
            if(j==0||S[i]==T[j]){ // 继续比较后面的字符
    			i++;
    			j++;
    		}
    		else
    			j=next[j]; // 模式串向右移动
        }
    	cout<<"一共比较了"<<sum<<"次"<<endl;
    	if(j>T[0]) // 匹配成功
    		return i-T[0];
    	else
    		return 0;
    }
    
    int main(){
    	SString S,T;
    	char str[100];
        cout<<"串S："<<"  ";
        cin>>str;//aabaaabaaaabea
    	StrAssign(S,str);//可以修改程序，自己输入字符串 
        cout<<"串T："<<"  ";
        cin>>str;//aaaab
    	StrAssign(T,str);
    	int *p=new int[T[0]+1]; //生成T的next数组
    	cout<<endl;
    	cout<<"BF算法运行结果："<<endl;
    	cout<<"主串和子串在第"<<Index_BF(S,T,1)<<"个字符处首次匹配\n";
    	cout<<endl;
    	cout<<"KMP算法运行结果："<<endl;
    	get_next(T,p);
    	cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n";
    	cout<<endl;
    	cout<<"改进的KMP算法运行结果："<<endl;
        get_next2(T,p);
    	cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n";
    	return 0;
    }

![Center 19][]

本文来自《趣学数据结构》，让数据结构变得简单有趣。

[Center]: /images/20220607/9930d54d9f2f415c8cd65a89cb2989b5.png
[Center 1]: /images/20220607/a05b6fc4ffab4f0ca3746914e6b68208.png
[Center 2]: /images/20220607/6871a825b4424b9ba6a37545787682be.png
[Center 3]: /images/20220607/858120d2551a47549ea90f37475e52f8.png
[Center 4]: /images/20220607/f7259e5370084817818f3aa8e6600315.png
[Center 5]: /images/20220607/a00792ff13894166b0d0f1dbbd2fdc2e.png
[Center 6]: /images/20220607/bad91542bbe64e7ab69ece076bd6a9d3.png
[Center 7]: /images/20220607/792a1adfd2c84c1dad00e3f55eeeed06.png
[Center 8]: /images/20220607/a2a8eeff10f94ed3ae5c3ee42fb046a0.png
[Center 9]: /images/20220607/ad21bc64dcd34e3e92e2845c988c699f.png
[Center 10]: /images/20220607/41416b729d21435cbb9ba88d77f15977.png
[Center 11]: /images/20220607/85526b9b848a43038780603876254e99.png
[Center 12]: /images/20220607/c48ae62f6fbf43698172e7b0bbb46505.png
[Center 13]: /images/20220607/7d88f4547a124055a6bbced96d2c5a70.png
[Center 14]: /images/20220607/8004fe54e42947f7b5ff7899509cf1eb.png
[Center 15]: /images/20220607/546929e553404eddb35e81f2643fd3d2.png
[Center 16]: /images/20220607/d6e4bac3b562437bad573b519cd8f29f.png
[Center 17]: /images/20220607/ceadb114e00d4bddacf21d38e9231210.png
[Center 18]: /images/20220607/d4280100e35444b0b5b49e5bffff5980.png
[Center 19]: /images/20220607/7c63ef8a5df84fc8a2880d346ab0fa16.png