字符串匹配kmp算法(首字母对应next数组的值为0)

速度:

0.5 1 2 5

算法概览

Copyright © 2018-2025 donghuasuanfa.com 动画算法 by 谷禾水 .All rights reserved

版权声明：本站原创文章、作品，未经本人许可，任何人或机构不得以任何形式对本站内容进行复制作商业用途.

    在计算机科学中，克努斯-莫里斯-普拉特字符串查找算法（英语：Knuth–Morris–Pratt algorithm，简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。这个算法由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。
    算法主要包含俩个步骤。
    1.计算部分匹配表：首先，根据模式串计算部分匹配表(next 数组)，作用是让算法无需多次匹配模式串中的任何字符。能够实现线性时间搜索的关键是在主串的一些字段中检查模式串的初始字段，可以确切地知道在当前位置之前的一个潜在匹配的位置。
    2.移动模式串位置：如果匹配失败，则按照移动步数移动模式串位置，无需重新逐个字符匹配。

    kmp计算next数组主要有俩种方法，常见的算法为首字母为0或首字母为-1俩种方式。此动画算法采用的计算规则为首字母为0，如果首字母采用-1的计算逻辑，则只需将next数组整体向右移一位。
    1.时间复杂度：KMP算法的总时间复杂度为 O(n + m)，其中：
        n 是主串（文本）的长度
        m 是模式串（要匹配的子串）的长度
    具体分为两个阶段：
        a.预处理阶段（构建next）：计算模式串的最长前缀后缀数组（如 LPS 或 next 数组），时间复杂度为 O(m)。
        b.匹配阶段：在主串中查找模式串，时间复杂度为 O(n)。

    2.空间复杂度：KMP算法的空间复杂度为 O(m)，主要用于存储前缀表（如 LPS 或 next 数组），其长度与模式串相同。