kmp算法和kmp的优化

以你之姓@ 2023-07-13 03:40 3阅读 0赞

#### 一、kmp是什么 ####

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

简单来说，就是在拿到一个模式串后，判断是否是主串的一个子序列，即主串是否包含模式串。最简单的方法就是把模式串的每一位和主串的每一位都挨个比较，但是这种方法虽然直接，但是太暴力了，时间复杂度高，效率低，因此，就有了kmp算法来优化他。

--------------------

#### 二、kmp算法主要思想 ####

一般，每一次模式串和主串匹配失败，又返回模式串的第一位和主串的下一位比较，而kmp则利用了此次匹配失败的信息，最快的找到下一个可能匹配上的地方。举个例子：  
设主串（记为s）为：a b c a b c a b d c 模式串（记为p）为：a b c a b d  
暴力算法匹配字符串过程中，我们会把s\[0\] 跟 p\[0\] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把s\[1\] 跟 p\[0\]再匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这样是不是很麻烦。

而在kmp中，我们会先对模式串计算出他的一个next数组，这个数组就相当于一个索引，如果这一位出错了，那么直接跳到索引指向的地方去比较，以减少匹配次数。那么索引怎么来找呢。  
我们主要来找模式串中**已匹配子串**的最大相同前后缀。首先，先介绍一下什么是前缀和后缀，用模式串p：a b a c a X来说，X之前的子串所有的前缀有5个：a,ab,abc,abca,abcab,后缀也有5个：bcabd,cabd,abd,bd,d  
那么有了最大相同前后缀，怎么用呢？举例来说：

此时s\[4\]的b与a\[4\]的a失配，模式串就会后移到他已匹配的前缀（a b）和后缀（a b）重叠的地方

我们只需要在匹配前，求出模式串的next数组，如果主串和模式串的第i个失配，这直接将next\[i\]和主串的这一位接着比较即可。

--------------------

#### 三、求next数组 ####

那么在理解了kmp算法的思想之后，那么最关键的next数组怎么求出呢？

void get_next(string p,int next[])
    { 
    	int i,m; //i为字符串下标，m为最大相同前后缀大小
    	next[0] = 0;
    	for(i = 1,m = 0;i < p.size();i++)	//i从前往后遍历模式串p
    	{ 
    		next[i] = m;	//m是上一层循环已经计算出的最大相同前后缀大小，在这直接赋值给next[i]
    		while(m > 0 && p[i] != p[m])	//如果p[i]和p[m]失配且m不在第一位，则把m打回去重新判断是否匹配直到把m打回开头
    		{ 
    			m = next[m-1];
    		}
    		if(p[i] == p[m])	//如果p[i]和p[m]匹配，则m（最大相同前后缀大小）加1
    		{ 
    			m++;
    		}
    	}
    }

<table> 
 <thead> 
  <tr> 
   <th>字符串</th> 
   <th>a</th> 
   <th>b</th> 
   <th>c</th> 
   <th>a</th> 
   <th>b</th> 
   <th>d</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>next数组</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

当模式串的第1个字符和主串s的第j个失配了，模式串后移一位，模式串的第1个和主串的j+1个比较  
当模式串的第i个和主串s的第j个失配了，直接将模式串的next\[i\]和主串s\[j\]比较

--------------------

#### 四、kmp判断子序列 ####

用kmp判断模式串p是否是主串s的子序列

void get_naxt(string p,int next[])
    { 
    	int i,m;
    	next[0] = 0;
    	for(i = 0,m = 0;i < p.size();i++)
    	{ 
    		while(m > 0 && p[i] != p[m])
    		{ 
    			m = next[m];
    		}
    		if(p[i] == p[m]
    		{ 
    			m++;
    		}
    		next[i] = m;
    	}
    }
    int kmp(string s,string p)
    { 
    	int i,j,next[99];
    	get_next(p,next);
    	for(i = 0,j = 0;i < s.size();i++)
    	{ 
    		while(j > 0 && s[i] != p[j])
    		{ 
    			j = next[j];
    		}
    		if(s[i] == p[j])
    		{ 
    			j++;
    		}
    		if(j == p.size())
    		{ 
    			return(i-j+1+1);
    		}
    	}
    	return -1;
    }
    
    int main()
    { 
    	int ans;
    	string s,p;
    	cin >> s >> p;
    	ans = kmp(s,p);
    	cout << ans;
    
    	return 0;
    }

--------------------

#### 五、kmp的优化 ####

kmp已经比较简便了，但有些特殊情况时依旧繁琐，比如主串是aaaabaaaac，模式串是aaaac

此时s\[4\]和p\[4\]不匹配，下一步移动到next\[4\]

此时再后移…  
直到模式串移到头才匹配主串的下一位，针对此我们对kmp加以优化，我们可以直接将相同的aaa的next都设为第一个a的next，这样就解决了此类情况，我们更新一下next函数

void get_next(string p,int next[])
    { 
    	int i,m; //i为字符串下标，m为最大相同前后缀大小
    	next[0] = 0;
    	for(i = 1,m = 0;i < p.size();i++)
    	{  
    		if(p[i] == p[m])
    			next[i] = next[m];
    		else
    			next[i] = m;
    		while(m > 0 && p[i] != p[m])
    		{ 
    			m = next[m-1];
    		}
    		if(p[i] == p[m])
    		{ 
    			m++;
    		}
    	}
    }

--------------------

\[1\].小白见解，有问题请指出。