字符串之KMP算法

谁借莪１个温暖的怀抱￠ 2021-09-11 01:54 427阅读 0赞

## **一、介绍** ##

KMP算法全称Knuth-Morris-Pratt算法，是一种字符串匹配算法，常规字符匹配是每次移动一位，复杂度O(mn)；而KMP算法复杂度O(m+n)。

## **二、算法原理** ##

KMP算法利用的是目标字符串（要匹配的字符串，如下图第二行）前后缀有相同的子字符串和在匹配过程中前i-1个字符已经匹配过的规律。  
**匹配过程：**  
![这里写图片描述][20160910144523501]  
**部分匹配表：**  
![这里写图片描述][20160910151903043]  
从第一张图中我们看到当我们目标字符串第一位与被匹配字符串字符相等时，我们向后移动指针，逐个匹配后面字符是否相等。当匹配字符Ｄ时，被匹配字符串为空字符，显然不等。这时与常规方法将目标字符串整体向后移动一位不同。ＫＭＰ算法根据部分匹配表，Ｄ前面字符为Ｂ，对于值为２，将字符串移动４位（**移动位数＝已经匹配字符ABDCAB长度6-字符B在部分匹配表中对应值2=4**），这是目标字符串前面的ＡＢ就移动到后面ＡＢ所在位置了。  
![这里写图片描述][20160910152019090]  
从上图变化中，我们看到了我们利用ABDCAB有相同前后缀AB，在我们比较到字符D位置后，字符串ABDCABD前面的字符串ABDCAB已经比较过了，利用这个信息，我们直接把前缀移动到后缀位置，完成移动K位。

> 关于此处为什么可以直接移动4位，我们已经匹配到第一张图所在位置，此时D匹配不符合。常规情况下我们后移一位，但是我们要明白往下移动一位我们仍要匹配到AB，也就是说如果后移一位后我们目标字符串从0位开始重新匹配，至少在相应位置上仍然需要AB。而KMP算法利用我们已经知道子字符串ABDCAB后缀有AB，而且我们已经匹配过了，知道接下来的AB在被匹配字符串上的位置。也就是说在AB前面的B，D，C位已经显然不可能匹配成功了。

## **三、部分匹配表** ##

前缀：除最后一个字符，前面字符的组合  
　　后缀：除第一个字符，后面字符的组合

> 　　如上图：目标字符串ABDCABD  
> 　　前缀有：\[A\] \[AB\] \[ABD\] \[ABDC\] \[ABDCA\] \[ABDCAB\]  
> 　　后缀有：\[D\] \[BD\] \[ABD\] \[CABD\] \[DCABD\] \[BDCABD\]

由前后缀的关系，我们可以算出一张表：  
　　对于字符串A：前后缀为空集，公共元素为0；  
　　对于字符串AB：前缀\[A\]，后缀\[B\]，公共元素为0；  
　　对于字符串ABD：前缀\[A\] \[AB\]，后缀\[BD\] \[D\]，公共元素为0；  
　　对于字符串ABDC：前缀\[A\] \[AB\] \[ABD\]，后缀\[BDC\] \[DC\] \[C\]，公共元素为0；  
　　对于字符串ABDCA：前缀\[A\] \[AB\] \[ABD\] \[ABDC\]，后缀\[BDCA\] \[DCA\] \[CA\] \[A\]，公共元素为1。长度为１；  
　　对于字符串ABDCAB：前缀\[A\] \[AB\] \[ABD\] \[ABDC\] \[ABDCA\]，后缀\[BDCAB\] \[DCAB\] \[CAB\] \[AB\] \[B\]，公共元素为1。长度为２；  
　　对于字符串ABDCA：前缀\[A\] \[AB\] \[ABD\] \[ABDC\] \[ABDCA\] \[ABDCAB\]，后缀\[D\] \[BD\] \[ABD\] \[CABD\] \[DCABD\] \[BDCABD\]，公共元素为1；长度为３；  
　　如下表：  
　　![这里写图片描述][20160910151903043]

> 这里必须是前缀和后缀相同。如果不是前缀而是中间缀的话我们就不能判断中间缀前面的字符能否跟被匹配字符串匹配上。所以需要从头开始，也就是从前缀开始匹配。

## **四、例题** ##

[LeetCode之Two Sum][LeetCode_Two Sum]

[20160910144523501]: /images/20210520/f3feacfa56d54ada8bc6d6917375aaf1.png
[20160910151903043]: /images/20210520/3207a8a9922a48a28148c8c90adc078c.png
[20160910152019090]: /images/20210520/27e72e681e164dbc98fe86328f540b9a.png
[LeetCode_Two Sum]: http://blog.csdn.net/qq_16234613/article/details/52691940