KMP算法详解及其Java实现

以你之姓@ 2021-12-11 05:59 274阅读 0赞

KMP算法，是一种改进的字符串模式匹配算法，可以在O(n+m)的时间复杂度以内完成字符串的匹配操作，其核心思想在于：当一趟匹配过程中出现字符不匹配时，不需要回溯主串的指针，而是利用已经得到的“部分匹配”，将模式串尽可能多地向右“滑动”一段距离，然后继续比较。

## 1. 朴素的字符串模式匹配算法 ##

求一个字符串（模式串）在另一个字符串（主串）中的位置，称为字符串模式匹配。

在朴素的字符串模式匹配算法中，我们对主串S和模式串T分别设置指针i和j，假设字符串下标从0开始，初始时i和j分别指向每个串的第0个位置。在第n趟匹配开始时，i指向主串S中的第n-1个位置，j指向模式串T的第0个位置，然后逐个向后比较。若T中的每一个字符都与S中的字符相等，则称匹配成功，否则，当遇到某个字符不相等时，i重新指向S的第n个位置，j重新指向T的第0个位置，继续进行第n+1趟匹配。

例如，我们对模式串T=“abaabcac”和主串S=“abcabaabaabcacb”进行匹配。如图1.1，此时正在进行第4趟匹配，S\[3...7\]与T\[0...4\]均相等，但当i=8，j=5时，S\[8\]与T\[5\]不相等，匹配失败。于是，置i=4，j=0，相当于将模式串向右移动一位后，重新开始下一趟匹配，如图1.2。

![图1.1][1.1]

图1.1 当i=8，j=5时，字符不相等，匹配失败

![图1.2][1.2]

图1.2 将模式串向右移动一位后，重新开始下一趟匹配

利用此种方法进行字符串匹配，最坏情况下时间复杂度为O(n\*m)，其中n和m分别为主串和模式串的长度。

## 2. 改进的字符串模式匹配算法——KMP算法 ##

在上面的例子中，我们可以看到，当i=8，j=5时，S\[8\]与T\[5\]不相等，于是置i=4，j=0，相当于将模式串向右移动一位，再开始下一趟匹配。然而，通过观察我们可以发现，之后的两趟匹配，即i=4，j=0以及i=5，j=0都是不必要的。这是因为，在之前的一趟匹配过程中，我们已经部分匹配了T的子串“abaab”。此时将T向右移动一位，则相当于对T中的“abaab……”与S中的“baab……”进行匹配，显然无法匹配成功。继续右移T，则相当于对T中的“abaab……”与S中的“aab……”进行匹配，依然无法匹配成功。只有当T向右移动3位后，此时对T中的“abaab……”与S中的“ab……”进行匹配，才会有成功的可能，也就有必要向后继续进行比较。如图2.1。

![图2.1][2.1]

图2.1 匹配失败时，将T向右移动3位后，才有继续比较的必要

因此，当i=8，j=5，T的子串“abaab”已经匹配成功，而其后一位字符却不相等时，不必回溯i指针，置i=8，j=2，继续向后比较，相当于将T向右移动3位，并从T的第3位开始向后比较。如图2.2。

![图2.2][2.2]

图2.2 匹配失败后，直接置i=8，j=2，继续向后比较

这就是KMP算法的基本思路。对于模式串T中的前j个字符组成的子串，设置数组next\[j\]存放一个值，当模式串T匹配至第j个字符时与主串不相等，则i指针不变，将j指针置为next\[j\]的值，然后继续进行比较。在上例中，串“abaab”为模式串T的前5个字符组成的子串，令next\[5\]=2，当i=8，j=5时，S\[8\]与T\[5\]不相等，于是置i=8，j=next\[j\]=next\[5\]=2，然后继续进行比较。

因此，KMP算法的核心在于求出数组next，即模式串T中每一个长度为j (0<j<T.length) 的前缀所对应的next\[j\]的值。

### next数组求解算法 ###

在求解next数组前，我们首先需要理解next数组的含义。回到前面的例子，当T的子串“abaab”的下一个字符与主串不相等时，主串的指针i不变，j回溯至2，指向T的第3个字符，其本质是因为串“abaab”的前缀和后缀有一个长度为2的最长公共串“ab”，因此我们省略了前缀“ab”和后缀“ab”的比较过程，直接对它们的后一个字符，即T\[2\]和S\[8\]进行比较。

再看另一个例子，假设有模式串T=“abacaabadad”，其已部分匹配完T\[0...7\]，即“abacaaba”，在匹配T\[8\]时遇到匹配失败，因T\[0...7\]的前缀和后缀有长度为3的最长公共串“aba”，因此next\[8\]=3，置j=next\[j\]=next\[8\]=3，i不变，然后从T\[3\]，即T的第4个字符开始比较。如图2.3。

![图2.3][2.3]

图2.3 匹配T\[8\]时失败，i不变，j回溯至3

总之，对于模式串T，next\[j\]代表了T的前j个字符组成的子串中，其前缀和后缀的最长公共串的长度。

求解字符串T的next数组的算法如下：

> 1.  next\[0\]=-1, next\[1\]=0。
> 2.  在求解next\[j\]时，令k=next\[j-1\]，
> 3.  比较T\[j-1\]与T\[k\]的值，
>     
>     > a. 若T\[j-1\]等于T\[k\]，则next\[j\]=k+1。
>     > 
>     > b. 若T\[j-1\]不等于T\[k\]，令k=next\[k\]，若k等于-1，则next\[j\]=0，否则跳至3。

下面以模式串T=“abaabcac”为例，给出求next数组的过程：

> 1.  next\[0\]=-1, next\[1\]=0。
> 2.  当j=2时，k=next\[j-1\]=next\[1\]=0，由于T\[j-1\]=T\[1\]=‘b’，T\[k\]=T\[0\]=‘a’，T\[j-1\]不等于T\[k\]，令k=next\[k\]=next\[0\]=-1，因此next\[2\]=0。
> 3.  当j=3时，k=next\[j-1\]=next\[2\]=0，由于T\[j-1\]=T\[2\]=‘a’，T\[k\]=T\[0\]=‘a’，T\[j-1\]等于T\[k\]，因此next\[3\]=k+1=1。
> 4.  当j=4时，k=next\[j-1\]=next\[3\]=1，由于T\[j-1\]=T\[3\]=‘a’，T\[k\]=T\[1\]=‘b’，T\[j-1\]不等于T\[k\]，令k=next\[k\]=next\[1\]=0。此时T\[k\]=T\[0\]=‘a’，T\[j-1\]等于T\[k\]，因此next\[3\]=k+1=1。
> 5.  当j=5时，k=next\[j-1\]=next\[4\]=1，由于T\[j-1\]=T\[4\]=‘b’，T\[k\]=T\[1\]=‘b’，T\[j-1\]等于T\[k\]，因此next\[5\]=k+1=2。
> 6.  当j=6时，k=next\[j-1\]=next\[5\]=2，由于T\[j-1\]=T\[5\]=‘c’，T\[k\]=T\[2\]=‘a’，T\[j-1\]不等于T\[k\]，令k=next\[k\]=next\[2\]=0。此时T\[k\]=T\[0\]=‘a’，T\[j-1\]不等于T\[k\]，再令k=next\[k\]=next\[0\]=-1，因此next\[6\]=0。
> 7.  当j=7时，k=next\[j-1\]=next\[6\]=0，由于T\[j-1\]=T\[6\]=‘a’，T\[k\]=T\[0\]=‘a’，T\[j-1\]等于T\[k\]，因此next\[7\]=k+1=1。

将next数组全部求出之后，只需在简单的匹配算法上稍作修改，便得到了KMP的匹配算法：当模式串T匹配至第j个字符时匹配失败，i指针不变，将j指针置为next\[j\]的值，若j的值为-1，则将i和j同时加1。随后继续进行逐个的比较。

下面以模式串T=“abaabcac”和主串S=“abcabaabaabcacb”进行匹配为例，给出KMP匹配算法的全过程。  
之前已经求得模式串T的next数组为\[-1, 0, 0, 1, 1, 2, 0, 1\]。

1.  初始时，i=0，j=0，匹配成功。
    
    ![1485189-20181107203144421-1790051929.png][]
2.  i=1，j=1，匹配成功。
    
    ![1485189-20181107203301705-1573255069.png][]
3.  i=2，j=2，匹配失败。
    
    ![1485189-20181107203312482-506404756.png][]
4.  i=2，j=next\[2\]=0，匹配失败。
    
    ![1485189-20181107203321486-1584379594.png][]
5.  i=2，j=next\[0\]=-1，匹配失败。
    
    ![1485189-20181107203329813-1181552146.png][]
6.  i=2+1=3，j=-1+1=0，匹配成功。
    
    ![1485189-20181107203345507-1570749968.png][]
7.  i=4，j=1，匹配成功。
    
    ![1485189-20181107203356011-1340913809.png][]
8.  i=5，j=2，匹配成功。
    
    ![1485189-20181107203406410-1127902417.png][]
9.  i=6，j=3，匹配成功。
    
    ![1485189-20181107203417066-1414119806.png][]
10. i=7，j=4，匹配成功。
    
    ![1485189-20181107203426091-1146892290.png][]
11. i=8，j=5，匹配失败。
    
    ![1485189-20181107203437862-1315035527.png][]
12. i=8，j=next\[5\]=2，匹配成功。
    
    ![1485189-20181107203448412-1574307342.png][]
13. 继续向后比较，中间过程均匹配成功，故不再赘述，当i=13，j=7时，模式串匹配完成。
    
    ![1485189-20181107203458300-1121595444.png][]

以上就是KMP匹配算法的全过程。总结一下，KMP算法的实质就是以空间换时间，在匹配之前将模式串的一些信息存储起来（next数组），在随后的匹配过程中利用这些信息减少不必要的匹配次数，以提高匹配效率。在实际的应用过程中，简单模式匹配算法的执行时间常常接近于KMP算法，仅当主串与模式串有很多“部分匹配”时，KMP算法才能显著提升性能。

## 3. KMP算法的Java实现 ##

下面给出KMP算法的Java代码。整个算法分为两部分，一是next数组的求解，二是KMP匹配过程。

> 1.  package pratice618;
> 2.  public class KMPtest \{
> 3.          /\*\*
> 4.           \* ycy
> 5.           \* 求出一个字符数组的next数组
> 6.           \* @param t 字符数组
> 7.           \* @return next数组，next\[0\]=-1,next\[1\]之后为最长公共长度。
> 8.           \*/
> 9.          public static int\[\] getNextArray(char\[\] str) \{
> 10.             int\[\] next = new int\[str.length\];
> 11.             next\[0\] = -1;  //首先将next\[0\]赋值为 -1，
> 12.             next\[1\] = 0;   //a前缀和后缀都是null，所以为0;
> 13.             int k;
> 14.             /\*
> 15.              \* next的值，为前一个next的值基础上，再比较新加一个字符和前面公共字符再加一个字符是否一样，
> 16.              \* 如果一样，next+1，否则next为0；
> 17.              \*/
> 18.             for (int j = 2; j < str.length; j++) \{
> 19.                 k=next\[j-1\];     
> 20.                 while (k!=-1) \{
> 21.                     if (str\[j - 1\] == str\[k\]) \{
> 22.                         next\[j\] = k + 1;
> 23.                         break;
> 24.                     \}
> 25.                     else \{
> 26.                         k = next\[k\];
> 27.                     \}
> 28.                     next\[j\] = 0;  //当k==-1而跳出循环时，next\[j\] = 0，否则next\[j\]会在break之前被赋值
> 29.                 \}
> 30.             \}
> 31.             for(int i=0;i<str.length;i++)
> 32.                 System.out.print(" "+next\[i\]);  //输出next数组
> 33.             System.out.println(" ");
> 34.             return next;
> 35.         \}
> 36.         /\*\*
> 37.          \* 对主串s和模式串t进行KMP模式匹配
> 38.          \* @param str 主串
> 39.          \* @param t 模式串
> 40.          \* @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1
> 41.          \*/
> 42.         public static int kmpMatch(String str, String t)\{
> 43.             char\[\] s\_arr = str.toCharArray();
> 44.             char\[\] t\_arr = t.toCharArray();
> 45.             int\[\] next = getNextArray(t\_arr);
> 46.             int i = 0, j = 0;
> 47.             while (i<s\_arr.length && j<t\_arr.length)\{
> 48.                 if(j == -1 || s\_arr\[i\]==t\_arr\[j\])\{
> 49.                     i++;
> 50.                     j++;
> 51.                 \}
> 52.                 else
> 53.                     j = next\[j\];  //需要移动的长度是：j-next\[j\]，即移动位数=已经匹配的个数-公共长度                
> 54.             \}
> 55.             if(j == t\_arr.length)
> 56.                 return i-j;
> 57.             else
> 58.                 return -1;
> 59.         \}
> 60.         public static void main(String\[\] args) \{
> 61.             String str = "abcabaabaabcacb";//主字符串
> 62.             String patt = "abaabcac";   //模式
> 63.             System.out.println(kmpMatch(str,patt));
> 64.         \}
> 65.     \}

转载：[https://www.cnblogs.com/imzhr/p/9613963.html][https_www.cnblogs.com_imzhr_p_9613963.html]

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[1.1]: /images/20211211/1ee44a35390a4353a72c11181e4f339f.png
[1.2]: /images/20211211/31dda43a00c7460bbe9f293e09d67a4b.png
[2.1]: /images/20211211/3be9dc4067a34a78b09d9a9f2145a402.png
[2.2]: /images/20211211/2b3d55d93ea341b69f50090bcf27116a.png
[2.3]: /images/20211211/413245ee8ac14f0d9b343472da92f9e4.png
[1485189-20181107203144421-1790051929.png]: /images/20211211/61b20975a65c425a85c5f865981758ab.png
[1485189-20181107203301705-1573255069.png]: /images/20211211/197ed3fe9bb24c3193cd3cf92fb397f7.png
[1485189-20181107203312482-506404756.png]: /images/20211211/a03aa175ac274f5092b9714e2c75e0aa.png
[1485189-20181107203321486-1584379594.png]: /images/20211211/74c7f895b0a34e4bbe9980f937f16c5c.png
[1485189-20181107203329813-1181552146.png]: /images/20211211/92cc22ad57834068844617a5356353fa.png
[1485189-20181107203345507-1570749968.png]: /images/20211211/b439079112c14b46b4f58222ae1b2d4b.png
[1485189-20181107203356011-1340913809.png]: /images/20211211/00d9b632777347a0bad1434eaa187c9e.png
[1485189-20181107203406410-1127902417.png]: /images/20211211/95aecbd2f23947c88ee68c6950ed3c65.png
[1485189-20181107203417066-1414119806.png]: /images/20211211/3af61f62cbb448baa62e52b81b3ac2ee.png
[1485189-20181107203426091-1146892290.png]: /images/20211211/fd1c82d5f00c4d5480f6730bc0129cfd.png
[1485189-20181107203437862-1315035527.png]: /images/20211211/2ff4f9f20fcc4111b7cf54f70e6184ad.png
[1485189-20181107203448412-1574307342.png]: /images/20211211/6e33a63127034373bbcd7848bfa428a0.png
[1485189-20181107203458300-1121595444.png]: /images/20211211/7dd0f34f86274e25a4b188423bb5e467.png
[https_www.cnblogs.com_imzhr_p_9613963.html]: https://www.cnblogs.com/imzhr/p/9613963.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211211/55d968bdf01a4825a773ba3598a745ec.png