KMP算法详解：NEXT数组构建与字符串匹配

KMP算法详解：NEXT数组构建与字符串匹配

引用

CSDN

1.

https://m.blog.csdn.net/ydxuan/article/details/143217407

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在一个文本串中查找一个模式串。与朴素的字符串匹配算法相比，KMP算法通过预处理模式串，避免了不必要的字符比较，从而提高了匹配效率。本文将详细介绍KMP算法的核心部分——NEXT数组的构建及其在字符串匹配中的应用。

NEXT数组构建

NEXT数组是KMP算法中的关键数据结构，用于存储模式串中每个位置的最长公共前后缀长度。下面是一个Python实现的KMP算法类，其中包含了NEXT数组的构建方法：

class KMP(object):
    def build_next(self, pattern):
        """
        :param pattern: 模式串
        :return: NEXT数组[最长公共前后缀]
        """
        NEXT = [0] * len(pattern)
        j, i = 0, 1     # 定义指针，i指针递增，多数情况下，j指代当前子串的最长公共前后缀
        while j < len(pattern):
            if pattern[i] == pattern[j]:    # 如果当前字符匹配成功
                j += 1          # 遍历到这里的子串“最长公共前后缀+1”
                NEXT[i] = j     # 更新当前子串的最长公共前后缀
                i += 1          # 更新next组后需要递增i继续定义下一个节点位置的next值
            else:
                # 如果不匹配，正常情况需要回溯到上一个节点定义的最小公共前后缀值，继续查看有没有更小的公共前后缀，直到回溯到j=0还是没有就设置为0
                if j != 0:
                    j = NEXT[j - 1]
                # 如果j等于0，说明我们无法再向前匹配，我们将next_array[i]设置为0，并递增i遍历查找下一个
                else:
                    NEXT[i] = 0
                    i += 1
        return NEXT

KMP搜索算法

在构建好NEXT数组后，我们就可以使用KMP算法进行字符串匹配了。下面是KMP搜索的具体实现：

    def KMP_search(self, text, pattern):
        """
        :param text: 主串
        :param pattern: 模式串
        :return: 索引
        """
        NEXT = self.build_next(pattern)
        n, m = len(text), len(pattern)
        i, j = 0, 0
        while i < n:    # 当主串遍历完成
            if text[i] == pattern[j]:
                i += 1
                j += 1
                if j == m:  # 如果都匹配且子串走到末尾，返回主串的当前子串起始位置
                    return i - j
            else:   # 如果不匹配
                if j == 0:  # 如果一开始第一个字符就不匹配，直接移动i
                    i += 1
                else:
                    j = NEXT[j - 1]     # 回溯
        return -1   # 匹配失败

算法示意图

通过上述代码和示意图，我们可以清晰地看到KMP算法的工作流程。首先通过build_next方法构建模式串的NEXT数组，然后在KMP_search方法中利用这个数组进行高效的字符串匹配。KMP算法的核心思想是通过预处理模式串，避免在匹配过程中进行不必要的回溯，从而提高匹配效率。