KMP模式匹配算法

怼烎@ 2023-09-23 14:03 141阅读 0赞

## 一、朴素的模式匹配算法 ##

> 给定字符串M和N，求M中是否包含N，如果包含，则返回N在M中的起始位置

对于上面这道题目，我们很容易就能想到如下解法：

M和N各自维护一个指针。  
![f74216ee41de24716d2775541d772642.png][]

首先P1指针向右遍历，寻找与P2指针相同的字符  
![80e20f0b554ea0d836adde83fac0e416.png][]

然后P2与P1同时向右移动，并一一比对所指字符是否相同  
![59eb6088ad24c2201a189d11ff5f2451.png][]

一旦遇到不相同的字符，则停止遍历。P2回到初始位置，P1则回到此轮遍历开始时的下一个位置，然后继续前面的过程。  
![c7d6b9b81c522b7fcc9fa48f192d5fac.png][]

直到找到完全匹配的位置  
![382becd571522c68683519a5d4433b76.png][]

代码如下

/// <summary>
    /// 朴素的匹配模式算法
    /// </summary>
    /// <param name="m"></param>
    /// <param name="n"></param>
    /// <returns></returns>
    private int Process1(string m,string n)
    {
        
    	if (m == null || n == null || m.Length < n.Length || n.Length <= 0)
    		return -1;
    	int p1=0, p2 = 0;
    
    	while (p1 < m.Length && p2 < n.Length)
    	{
        
    		// 两字符相同,指针共同后移
    		if (m[p1] == n[p2])
    		{
        
    			p1++;
    			p2++;
    		}
    		// 两字符不同,指针回退
    		else
    		{
        
    			p1 = p1 - p2 + 1;
    			p2 = 0;
    		}
    	}
    	// 如果p2走到末尾,则匹配成功
    	if (p2 == n.Length)
    		return p1 - p2;
    	// 否则匹配失败
    	return -1;
    }

显然这种匹配方式的效率并不高，因为每当匹配失败，都需要进行回溯并重新开始匹配。假如给定的字符串分别为M=”0000000000000000000000001“、N=”0000001“这种类型的数据，那么其时间复杂度可想而知。事实上在最差情况下，这种算法的时间复杂度会达到 O ( N × M ) O(N×M) O(N×M)级别。

## 二、KMP模式匹配算法 ##

从前面的例子我们可以看出，朴素的模式匹配算法的根本问题在于：对于已经匹配过的片段没有进行记忆。

比如在进行下面的步骤时，我们首先匹配了“abcd“四个字符，到第五个字符时发现不匹配。  
![b1ba30104b6529485fec427388424148.png][]

于是我们将P1指针挪回了“b”的位置，并重新开始匹配。  
![5548e04145340a7f0455826aa77a76eb.png][]

但事实上，字符串N中，没有任何一个字符与开头的“a”相同。而在上一轮匹配中，我们已经确定，所匹配内容的前四个字符是相同的。所以后面的“bcd”是一定不会匹配上N的。也就是说我们可以直接跳到“f”的位置继续进行匹配  
![eba5680edbfa60846b77053e9b3094c5.png][]

那么如果N字符串中存在相同的字符又会怎样呢？来看下面这个例子

首先，当P1指针遍历到“f”字符时，匹配失败。但此时，N字符串中有与开头相同的字符“a”。也就是说，此时P1从第二个a开始匹配，是有可能匹配成功的。  
![ddbeb9c7f011bb23ebfb2a6dfe304608.png][]  
![2dcdd3b7563ead26f4ca58cdf318caf4.png][]

此时，我们站在上帝视角可以看出，之后的“ab”字符也是相同的，无需匹配。但在计算机视角，它在没有真正进行比较时是无法确定后面两个字符是相同的。所以我们需要证明出来。

证明起来也很简单，根据已知条件，N字符串中的红框部分和绿框部分是相同的。根据前一轮匹配可以得知，M字符串中蓝色的部分和N字符串中绿色的部分是相同的。很显然，蓝色框的部分与红色框的部分是一定相同的。  
![71b63d496af8e998a23d7c25806add81.png][]

根据结论，我们又可以省下两次匹配，现在只需要在如下位置继续进行匹配就可以了  
![e9974bab108afeff4febccfc799aa10b.png][]

在搞清楚上面两个例子之后，我们就可以总结规律了：

*  首先，对于P1指针来说，无论上述哪种情况，都是从不相等的字符处开始匹配
 *  对于P2指针的位置，主要取决于N字符串的数据情况。如果N字符串中没有重复字符，则会挪回到起始位置；如果N中有重复的字符串，就需要计算应该挪动到哪个位置。

现在问题聚焦在了“如果N存在重复字符串，P2该挪动到哪个位置”上。根据前面的例子，我们可以发现，这实际上就是求：当前匹配位置之前的字符串中，前缀与后缀相同的子串的最大长度。

可能有些难以理解，我们再通过几个例子来说明

首先是前面刚讲过的例子。此时P1与P2的字符不匹配。所以我们来求P1之前的字符串中，前缀与后缀相同的最大长度。  
![ddbeb9c7f011bb23ebfb2a6dfe304608.png][]

很显然，前后缀相同的最长子串就是“ab”，因此这个值为2。即P2挪动到下标为2的位置。  
![cce92436f8cf91176e02ee5b9d031da2.png][]

再来个极端点的例子  
![0f9de12b357e5ffe13eb18ef8082e388.png][]

P2之前，前后缀相同的最长子串是“aaaa”，长度为4，所以P2挪动到下标为4的位置  
![4d88c8f90508423b1f46088c1b0ca14a.png][]

此时P1与P2仍然不相等，所以继续计算P2之前的前后缀相同最长子串的长度。结果是3，所以P2移动到下标为3的位置。  
![633661fc58dae8fd264c574231a1c2f4.png][]

。。。。

也就是说，我们需要事先计算出N字符串中，各个位置对应的前后缀相同的最长子串长度。我们把它存到一个数组中，命名为next。为了简化表达，下面的“前后缀相同的最长子串长度”统一用`L`表示。

那么next数组怎么求呢？还是拿具体的例子来说明  
![e250cdb36ef5ef692ee5b1de61e61018.png][]

首先，next数组的第0位置是没有意义的，因为它对应的是N字符串中第0位置之前的`L`值，而第0位置之前是没有子串的。所以我们把它规定为-1。  
![692eb0fe3e5c9dde5be52c3b91beacdc.png][]

接下来right指针右移一位，来计算“b”之前的`L`值。但“b”之前只有一个字符“a”，所以要求的长度为0。  
![69e52fb551fa826078eadb130cef3cc1.png][]

right继续右移。此时需要求“ab”字符串的`L`值。很显然，也是0。  
![9783e50ebf63aec598e22ff358f2737a.png][]

right继续右移。此时要求“aba”字符串的`L`值。很显然，前后的“a”是相同的，所以这里的next值为1。  
![781c35bc004c2ddac634386705c812a6.png][]

因为我们之前已经找到了一对相同的前后缀，所以left指针也要后移。意思是我们现在处于“Combo”状态，只要下一对字符仍然是相同的，说明这对相同前后缀的子串还在继续延长。如果下一对字符不同了，那我们的“Combo”状态就断了，就得重新开始匹配相同前后缀的子串了。  
![3d1945a6ead7dd88acba3a49b4c56b41.png][]

果然，此时left指针所指的字符与right所指的字符相同，也就是说`L`值增加到了2。  
![5834457dead88e5ad548d80e6a31ce06.png][]

left和right指针一起右移。但这次就没这么幸运了，left和right的字符不相等了，我们的“Combo”中断了。  
![d4a32f4a745ec694d317e9b735e34e19.png][]

所以left指针要进行回溯。回溯到“Combo”之前的位置，也就是next\[left\]的位置。  
![a8457da7fc13b2f3247ed47fa60829ba.png][]

很可惜，即便left进行了回溯，也无法与right进行匹配。而且left已经无法继续向前回溯，所以`L`值为0。  
![547956ae7ec913633344ca941ee2b907.png][]

之后的步骤与前面类似，就不再赘述了，直接上代码：

/// <summary>
    /// 获取next数组
    /// </summary>
    /// <param name="n"></param>
    /// <returns></returns>
    private int[] GetNextArr(string n)
    {
        
    	int[] next = new int[n.Length];
    	// 0和1位置的值是固定的
    	next[0] = -1;
    	next[1] = 0;
    	// 定义左右指针
    	int left = 0, right = 1;
    	
    	while (right < n.Length-1)
    	{
        
    		// 字符匹配成功时,left、right同时右移,
    		// ‘前后缀相同的最长子串长度’+1(其实就是left的值)
    		if (n[left] == n[right])
    		{
        
    			left++;
    			next[right + 1] = left;
    			right++;
    		}
    		// 如果匹配失败,但left还没回溯到最开始的位置,那就继续回溯
    		else if (left > 0)
    		{
        
    			left = next[left];
    		}
    		// left回溯到0的位置也没有匹配成功,则‘前后缀相同的最长子串长度’为0
    		else
    		{
        
    			next[right + 1] = 0;
    			right++;
    		}
    	}
    	return next;
    }

有了next数组，我们在进行匹配时，就可以按照next数组对p2指针进行回溯了。代码如下：

/// <summary>
    /// KMP算法
    /// </summary>
    /// <param name="m"></param>
    /// <param name="n"></param>
    /// <returns></returns>
    private int Process2(string m, string n)
    {
        
    	if (m == null || n == null || m.Length < n.Length || n.Length <= 0)
    		return -1;
    	int p1 = 0, p2 = 0;
    	int[] next = GetNextArr(n);
    	while (p1 < m.Length && p2 < n.Length)
    	{
        
    		// 如果匹配成功,两指针都后移
    		if (m[p1] == n[p2])
    		{
        
    			p1++;
    			p2++;
    		}
    		// 如果匹配失败,且p2本来就在0位置,则p1后移
    		else if (p2 == 0)
    		{
        
    			p1++;
    		}
    		// 如果匹配失败,且p2不在0位置,则进行回溯
    		else
    		{
        
    			p2 = next[p2];
    		}
    	}
    	// p2遍历完成,说明匹配成功,否则匹配失败
    	return p2 == n.Length ? p1 - p2 : -1;
    }

[f74216ee41de24716d2775541d772642.png]: https://img-blog.csdnimg.cn/img_convert/f74216ee41de24716d2775541d772642.png
[80e20f0b554ea0d836adde83fac0e416.png]: https://img-blog.csdnimg.cn/img_convert/80e20f0b554ea0d836adde83fac0e416.png
[59eb6088ad24c2201a189d11ff5f2451.png]: https://img-blog.csdnimg.cn/img_convert/59eb6088ad24c2201a189d11ff5f2451.png
[c7d6b9b81c522b7fcc9fa48f192d5fac.png]: https://img-blog.csdnimg.cn/img_convert/c7d6b9b81c522b7fcc9fa48f192d5fac.png
[382becd571522c68683519a5d4433b76.png]: https://img-blog.csdnimg.cn/img_convert/382becd571522c68683519a5d4433b76.png
[b1ba30104b6529485fec427388424148.png]: https://img-blog.csdnimg.cn/img_convert/b1ba30104b6529485fec427388424148.png
[5548e04145340a7f0455826aa77a76eb.png]: https://img-blog.csdnimg.cn/img_convert/5548e04145340a7f0455826aa77a76eb.png
[eba5680edbfa60846b77053e9b3094c5.png]: https://img-blog.csdnimg.cn/img_convert/eba5680edbfa60846b77053e9b3094c5.png
[ddbeb9c7f011bb23ebfb2a6dfe304608.png]: https://img-blog.csdnimg.cn/img_convert/ddbeb9c7f011bb23ebfb2a6dfe304608.png
[2dcdd3b7563ead26f4ca58cdf318caf4.png]: https://img-blog.csdnimg.cn/img_convert/2dcdd3b7563ead26f4ca58cdf318caf4.png
[71b63d496af8e998a23d7c25806add81.png]: https://img-blog.csdnimg.cn/img_convert/71b63d496af8e998a23d7c25806add81.png
[e9974bab108afeff4febccfc799aa10b.png]: https://img-blog.csdnimg.cn/img_convert/e9974bab108afeff4febccfc799aa10b.png
[cce92436f8cf91176e02ee5b9d031da2.png]: https://img-blog.csdnimg.cn/img_convert/cce92436f8cf91176e02ee5b9d031da2.png
[0f9de12b357e5ffe13eb18ef8082e388.png]: https://img-blog.csdnimg.cn/img_convert/0f9de12b357e5ffe13eb18ef8082e388.png
[4d88c8f90508423b1f46088c1b0ca14a.png]: https://img-blog.csdnimg.cn/img_convert/4d88c8f90508423b1f46088c1b0ca14a.png
[633661fc58dae8fd264c574231a1c2f4.png]: https://img-blog.csdnimg.cn/img_convert/633661fc58dae8fd264c574231a1c2f4.png
[e250cdb36ef5ef692ee5b1de61e61018.png]: https://img-blog.csdnimg.cn/img_convert/e250cdb36ef5ef692ee5b1de61e61018.png
[692eb0fe3e5c9dde5be52c3b91beacdc.png]: https://img-blog.csdnimg.cn/img_convert/692eb0fe3e5c9dde5be52c3b91beacdc.png
[69e52fb551fa826078eadb130cef3cc1.png]: https://img-blog.csdnimg.cn/img_convert/69e52fb551fa826078eadb130cef3cc1.png
[9783e50ebf63aec598e22ff358f2737a.png]: https://img-blog.csdnimg.cn/img_convert/9783e50ebf63aec598e22ff358f2737a.png
[781c35bc004c2ddac634386705c812a6.png]: https://img-blog.csdnimg.cn/img_convert/781c35bc004c2ddac634386705c812a6.png
[3d1945a6ead7dd88acba3a49b4c56b41.png]: https://img-blog.csdnimg.cn/img_convert/3d1945a6ead7dd88acba3a49b4c56b41.png
[5834457dead88e5ad548d80e6a31ce06.png]: https://img-blog.csdnimg.cn/img_convert/5834457dead88e5ad548d80e6a31ce06.png
[d4a32f4a745ec694d317e9b735e34e19.png]: https://img-blog.csdnimg.cn/img_convert/d4a32f4a745ec694d317e9b735e34e19.png
[a8457da7fc13b2f3247ed47fa60829ba.png]: https://img-blog.csdnimg.cn/img_convert/a8457da7fc13b2f3247ed47fa60829ba.png
[547956ae7ec913633344ca941ee2b907.png]: https://img-blog.csdnimg.cn/img_convert/547956ae7ec913633344ca941ee2b907.png