kmp算法的流程图解（KMP算法：一种高效的字符串匹配算法）

KMP算法：一种高效的字符串匹配算法

介绍KMP算法

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，通过在匹配过程中利用已匹配的信息，可以避免不必要的匹配操作。该算法由科学家Donald Knuth、Vaughan Pratt及James Morris于1977年共同提出，算法时间复杂度为O(n+m)，其中n、m分别为模式串及文本串长度。

KMP算法的核心思想：

在匹配过程中，对于已匹配部分所对应的前缀与后缀信息，KMP算法可以根据该信息，通过移动模式串的指针，使得匹配过程可以跳过部分无需匹配的字符。 举个例子：如下所示的模式串\"ABCDABD\"  在匹配文本串时，如果模式串匹配到了\"D\"字符，则显然在此之前的\"ABCDAB\"已经匹配成功，此时如果暴力移动模式串的指针，重新从\"A\"字符开始匹配，时间复杂度显然较高。 而利用KMP算法，我们可以事先计算出模式串每个字符所对应的前缀后缀匹配信息，并根据该信息，将模式串指针直接移动到对应位置继续匹配，如下图所示：  从对比可以看出，KMP算法只需移动模式串的指针到\"B\"字符上即可，避免了重新匹配的过程，极大地提高了匹配效率。

KMP算法的流程图解：

1. 初始化原始匹配状态j=0、i=1 2. 从文本串首字符开始一直到末尾字符，进行如下操作： a. 当匹配成功时，移动模式串指针j=j+1，文本串指针i=i+1； b. 当匹配失败时，利用已匹配部分所对应的前缀后缀匹配信息kmp[j]，将模式串指针j向前移动，即j=kmp[j]，直到j不再匹配则终止。 c. 若模式串匹配完毕则说明匹配成功结束，返回当前匹配位置。 3. 匹配失败，则返回匹配失败结果。 以上按步骤所述即为KMP算法的详细执行过程，下面针对算法具体实现过程，进行更详尽的解析。

算法实现：

1.初始化KMP数组 根据上述分析，KMP算法的核心在于采用已匹配字符所对应的前缀后缀匹配信息，因此需要首先计算出模式串的前缀后缀匹配信息，并将信息存储在一个KMP数组中。代码如下所示： ```html function getKmpArr(str) { let kmpArr = new Array(str.length), j = 0, i = 1; kmpArr[0] = 0; while(i < str.length) { if(str[i] === str[j]) { kmpArr[i] = j + 1; i++; j++; } else if(j === 0) { kmpArr[i] = 0; i++; } else { j = kmpArr[j-1]; } } return kmpArr; } ``` 该代码采用循环判断法，首先初始化模式串的第一个字符的匹配信息为0，然后从模式串的第二个字符开始，循环执行以下操作： 1.若模式串的第i个字符与模式串的第j个字符相同时，则根据此前缀后缀匹配信息，将kmp[i]赋值为j+1。 2.如果模式串的第i个字符与模式串的第j个字符不相等，且j不为0，则根据已匹配部分所对应的前缀后缀匹配信息，设置j=kmp[j-1]。 3.如果都不满足上述两种情况，kmp[i]赋值为0。 2.匹配过程 根据前文所述流程，KMP算法匹配过程既可以采用递归方法，也可以采用循环迭代方法，为了更好地说明算法过程，以下将采用循环迭代方法进行解释。 ```html function kmpSearch(str, pattern) { let i = 0, j = 0, kmpArr = getKmpArr(pattern), len1 = str.length, len2 = pattern.length; while(i < len1 && j < len2) { if(str[i] === pattern[j]) { i++; j++; } else if (j === 0) { i++; } else { j = kmpArr[j-1]; } } if(j === len2) { return i - len2; } return -1; } ``` 在匹配过程中，需要比较文本串str与模式串pattern是否存在匹配。将文本串指针设置为i，初始值为0；将模式串指针设置为j，初始值为0；将KMP数组设置为kmpArr；文本串和模式串的长度分别为len1和len2。逐个移动文本串的指针，直到匹配成功或失败为止。 1.若当前文本串的指针所指字符和模式串的指针所指字符相同，则同时将文本串指针i和模式串指针j往后移动一位。 2.若当前文本串的指针所指字符和模式串的指针所指字符不同，且模式串指针已经指向了起始位置，则将文本串指针i往后移动一位再次进行匹配。 3.若当前文本串的指针所指字符和模式串的指针所指字符不同，且模式串指针不是起始位置，则根据已匹配部分所对应的前缀后缀匹配信息，将模式串指针向前移动到kmp[j-1]处，继续进行匹配。 4.当模式串指针j已经走到字符串末尾，则说明已经匹配成功，返回当前匹配位置i - len2。 5.当文本串指针i走到字符串末尾，而模式串仍未匹配完，则说明匹配失败，返回-1。 经过上述讲解，相信读者已经初步掌握了KMP算法的流程及实现，下面将对KMP算法的优缺点进行简单介绍，进一步说明该算法的重要性及应用现状。

KMP算法的优缺点：

优点： 1.算法时间复杂度为O(n+m)，相较于暴力枚举法的O(n*m)，时间复杂度显著降低。 2.通过已匹配字符所对应的前缀后缀匹配信息，可快速跳过不必要的匹配操作，提高匹配效率。 3.具有较好的泛化性，适用于多种文本字符串匹配任务。 缺点： 1.算法实现较为复杂，需要较高的算法功底以及思维难度。 2.在最坏情况下，算法时间复杂度依旧无法避免，基于此可能存在退化情况。 3.模式串的空间开销较大，需要创建一个KMP数组进行存储。 总结： KMP算法作为一种高效的字符串匹配算法，具有着广泛的应用场景，如匹配搜索引擎中文本查找、字符串编辑器查询等。虽然算法实现过程较为复杂，但是在应用中仍具有较高的优越性，值得广泛关注及学习。