C语言KMP算法简单示例和实现原理探究

概述

KMP算法是一种字符串匹配算法，它能在O(n+m)的时间复杂度内匹配文本串和模式串。与简单的暴力匹配算法相比，它的时间复杂度更低。

实现原理

暴力匹配算法

在了解KMP算法之前，我们先来看一下暴力匹配算法，这是最简单的字符串匹配算法。

暴力匹配算法的实现原理是：假设文本串为T，模式串为P，从T的第一个字符开始，依次比较T和P的每个字符，如果相同，则接着比较下一个字符，如果不同，则从下一个字符重新开始匹配，直到将整个模式串匹配完为止。

KMP算法

KMP算法是一种比暴力匹配算法更高效的字符串匹配算法。它的核心思想是：当出现不匹配时，尽可能地利用已经匹配过的部分，减少模式串和文本串比较的次数。

计算最长公共前缀和最长公共后缀

KMP算法的第一步是计算出模式串的“最长公共前缀”和“最长公共后缀”。

最长公共前缀指的是，以模式串开头的那部分子串中，既是前缀又是后缀的最长子串。例如，模式串“abab”的最长公共前缀是“ab”。

最长公共后缀指的是，以模式串结尾的那部分子串中，既是前缀又是后缀的最长子串。例如，模式串“abab”的最长公共后缀是“ab”。

计算最长公共前缀和最长公共后缀的方法是，以模式串中每个字符为结尾，找到它前面的子串中既是前缀又是后缀的最大长度。此处使用一个next数组来存储最长公共前缀和最长公共后缀的值。

KMP算法实现流程

有了最长公共前缀和最长公共后缀的值之后，就可以开始实现KMP算法了。KMP算法的实现流程如下：

• 从文本串T的第一个字符开始匹配模式串P的第一个字符。
• 如果两个字符相等，则继续比较下一个字符。
• 如果两个字符不相等，则根据next数组移动模式串。
• 重复步骤2和步骤3，直到找到匹配或者文本串匹配完为止。

KMP算法的关键在于如何根据next数组移动模式串。

假设文本串T的当前位置是i，模式串P的当前位置是j，出现不匹配时，模式串需要移动的距离是k = j - next[j]。移动模式串的时候，需要将模式串的前k个字符跳过，从第k+1个字符开始继续比较。

关于next数组的计算

next数组的第一个元素next[0]必须是-1，表示移动模式串到第一个字符之前。next数组的其他元素计算方法如下：

• next[0] = -1
• 如果模式串的前j个字符（不包括第j个字符）与模式串的前k个字符（不包括第k个字符）匹配，则next[j] = k。
• 如果模式串的前j个字符（不包括第j个字符）与模式串前缀的一个子串匹配，则递归地寻找匹配的最大长度，即next[k]。

示例

示例1

有一个文本串T：“ABCDABD”，和一个模式串P：“ABD”。

模式串P和文本串T的匹配过程如下：

1. T[1]和P[1]相等，继续比较下一个字符；
2. T[2]和P[2]相等，继续比较下一个字符；
3. T[3]和P[3]不相等，根据next数组将P向右移动2个字符（即跳过AB），改成在T[3]和P[1]比较。
4. T[3]和P[1]不相等，继续向右移动模式串，变成在T[3]和P[0]比较（即P前面加一个未匹配的字符）。
5. T[3]和P[0]不相等，因为next[0]=-1，所以将模式串P向右移动1个字符；
6. 继续比较T[3]和P[1]，相等，继续比较下一个字符；
7. T[4]和P[2]相等，继续比较下一个字符；
8. T[5]和P[3]相等，完成匹配。

示例2

有一个文本串T：“ACABAABAACACAADABAA”，和一个模式串P：“AABAAC”。

模式串P和文本串T的匹配过程如下：

1. T[1]和P[1]相等，继续比较下一个字符；
2. T[2]和P[2]相等，继续比较下一个字符；
3. T[3]和P[3]不相等，根据next数组将P向右移动3个字符（即跳过AAB），改成在T[3]和P[1]比较。
4. T[3]和P[1]不相等，继续向右移动模式串，变成在T[3]和P[0]比较（即P前面加一个未匹配的字符）。
5. T[3]和P[0]不相等，因为next[0]=-1，所以将模式串P向右移动1个字符；
6. 继续比较T[3]和P[1]，相等，继续比较下一个字符；
7. T[4]和P[2]相等，继续比较下一个字符；
8. T[5]和P[3]相等，继续比较下一个字符；
9. T[6]和P[4]相等，继续比较下一个字符；
10. T[7]和P[5]相等，完成匹配。

总结

KMP算法是一种高效的字符串匹配算法。通过计算模式串的最长公共前缀和最长公共后缀，可以减少模式串和文本串比较的次数，提高匹配效率。在实际开发中，可以使用KMP算法来实现字符串匹配功能，例如搜索引擎中的关键字查询等。