字符串匹配终极武器KMPPHP-Data-Structure-and-Algorithms中模式匹配算法逐步推演【免费下载链接】PHP-Data-Structure-and-AlgorithmsA repository with implementations of different data structures and algorithms using PHP项目地址: https://gitcode.com/gh_mirrors/ph/PHP-Data-Structure-and-Algorithms在 PHP-Data-Structure-and-Algorithms 这个 PHP 数据结构与算法仓库中KMP 字符串匹配算法是模式匹配部分的核心实现。本文带你从暴力匹配的痛点出发一步步手工推演 KMP 的前缀表LPS和匹配过程彻底搞懂这个 O(NM) 的字符串匹配神器为什么快、快在哪。为什么暴力匹配会慢O(N×M) 的坑先看仓库里同目录的朴素匹配实现 PatternMatching.php核心思路把模式串在每个位置逐字符比对一旦失配就整体右移一位从头再来。用示例文本AABAACAADAABABBBAABAA和模式串AABA暴力匹配遇到AC...、AD...这类匹配了一部分又失败的场景时已比较过的字符就全部白费了。最坏时间复杂度为O(N×M)——文本越长、模式串越长差距越夸张。 KMP 的核心思想只有一句话失配时利用模式串自身的重复信息跳过主文中已被排除的位置绝不让主文指针回退。上手代码项目中的 KMP 算法文件算法实现位于Algorithms/Recursion-DP-Others/KMPMatching.php它包含两个关键函数函数作用computeLPS()构建前缀表 LPSLongest Prefix Suffix记录每个位置最长相等前后缀长度kmpStringMatching()利用 LPS 表完成全匹配返回所有命中位置配套示例数据与朴素匹配版完全一致方便你对比两种算法的表现。第一步手绘 LPS 表以模式串 AABA 为例LPS 表的规则lps[0] 0之后逐位比较当前最长前后缀的下一个字符与当前位置字符。模式串A A B A下标 0~3步骤比较结果lps初始化——[0, ?, ?, ?]i1Avs 下标0的A相等长度1[0, 1, ?, ?]i2Bvs 下标1的A失配回退到 lps[0]0 再比BvsA仍失配[0, 1, 0, ?]i3Avs 下标0的A相等长度1[0, 1, 0, 1]最终 LPS 表[0, 1, 0, 1]这张表回答了一个关键问题当模式串的前 j 个字符已匹配成功、第 j1 个字符失配时可以从哪继续答案是回退到lps[j-1]位置——即最长公共前后缀处。第二步KMP 如何用 LPS 表跳过匹配匹配阶段只用两个指针i指向主文、j指向模式串。三条规则对应源码中的三分支逻辑字符相等i、j同时前进一步j 达到模式串长度 M记录命中位置i - j然后j lps[j-1]继续找下一处命中字符失配j ! 0时j lps[j-1]主文指针不回退j 0时i前进一位关键在于规则 3失配时只移动模式串指针主文指针i永不后退。以文本AABAACAADAABABBBAABAA为例当主文走到AC...时时刻主文[i]模式[j]动作已匹配 AAB 后CB失配j lps[2] 0重试CA失配j0 → i 前进下一位AA重新对齐继续暴力匹配在这一步要把模式串整体右移重比 3 个字符KMP 直接利用 LPS 表一步到位。第三步跑通完整匹配验证命中位置运行Algorithms/Recursion-DP-Others/KMPMatching.php输出Pattern found at index : 0 Pattern found at index : 9对照原文本验证A A B A A C A A D A A B A B B B A A B A A 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 └AABA┘ └AABA┘ 命中0 命中9两处命中AABA的位置下标 0 和 9被准确找出且算法只需一次正向扫描即可完成。KMP 复杂度对比一眼看懂快多少算法时间复杂度空间复杂度失配代价朴素匹配PatternMatching.phpO(N×M)O(1)已比较字符全部重来KMPKMPMatching.phpO(NM)O(M)借助 LPS 表直接跳转LPS 构建耗时 O(M)匹配扫描耗时 O(N)两者相加就是 O(NM)。对于模式串较长、主文极长的场景日志检索、病毒特征码扫描、DNA 序列比对优势是数量级的。延伸阅读仓库中更多模式匹配相关实现仓库Algorithms/Recursion-DP-Others/目录下还有几个值得对照学习的文件Algorithms/Recursion-DP-Others/PatternMatching.php—— 朴素模式匹配KMP 的对照组Algorithms/Recursion-DP-Others/DNASequencing.php—— Needleman-Wunsch 序列比对KMP 思想在生物信息中的近亲应用Algorithms/Recursion-DP-Others/LCS.php—— 最长公共子序列理解利用重叠信息加速的另一典型案例配合仓库 README 中的 Dynamic Programming and Others 章节可以把 KMP、朴素匹配、序列比对放在一起对比学习快速建立对整类字符串算法的完整认知。总结KMP 之所以被称为字符串匹配的终极武器秘密全在 LPS 表——一次 O(M) 的预处理换来了主文指针永不回退的 O(NM) 总复杂度。动手把AABA的 LPS 表[0,1,0,1]画一遍、再把上表的匹配轨迹走一遍你就真正掌握了它。【免费下载链接】PHP-Data-Structure-and-AlgorithmsA repository with implementations of different data structures and algorithms using PHP项目地址: https://gitcode.com/gh_mirrors/ph/PHP-Data-Structure-and-Algorithms创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 字符串匹配终极武器KMP：PHP-Data-Structure-and-Algorithms中模式匹配算法逐步推演
字符串匹配终极武器KMPPHP-Data-Structure-and-Algorithms中模式匹配算法逐步推演【免费下载链接】PHP-Data-Structure-and-AlgorithmsA repository with implementations of different data structures and algorithms using PHP项目地址: https://gitcode.com/gh_mirrors/ph/PHP-Data-Structure-and-Algorithms在 PHP-Data-Structure-and-Algorithms 这个 PHP 数据结构与算法仓库中KMP 字符串匹配算法是模式匹配部分的核心实现。本文带你从暴力匹配的痛点出发一步步手工推演 KMP 的前缀表LPS和匹配过程彻底搞懂这个 O(NM) 的字符串匹配神器为什么快、快在哪。为什么暴力匹配会慢O(N×M) 的坑先看仓库里同目录的朴素匹配实现 PatternMatching.php核心思路把模式串在每个位置逐字符比对一旦失配就整体右移一位从头再来。用示例文本AABAACAADAABABBBAABAA和模式串AABA暴力匹配遇到AC...、AD...这类匹配了一部分又失败的场景时已比较过的字符就全部白费了。最坏时间复杂度为O(N×M)——文本越长、模式串越长差距越夸张。 KMP 的核心思想只有一句话失配时利用模式串自身的重复信息跳过主文中已被排除的位置绝不让主文指针回退。上手代码项目中的 KMP 算法文件算法实现位于Algorithms/Recursion-DP-Others/KMPMatching.php它包含两个关键函数函数作用computeLPS()构建前缀表 LPSLongest Prefix Suffix记录每个位置最长相等前后缀长度kmpStringMatching()利用 LPS 表完成全匹配返回所有命中位置配套示例数据与朴素匹配版完全一致方便你对比两种算法的表现。第一步手绘 LPS 表以模式串 AABA 为例LPS 表的规则lps[0] 0之后逐位比较当前最长前后缀的下一个字符与当前位置字符。模式串A A B A下标 0~3步骤比较结果lps初始化——[0, ?, ?, ?]i1Avs 下标0的A相等长度1[0, 1, ?, ?]i2Bvs 下标1的A失配回退到 lps[0]0 再比BvsA仍失配[0, 1, 0, ?]i3Avs 下标0的A相等长度1[0, 1, 0, 1]最终 LPS 表[0, 1, 0, 1]这张表回答了一个关键问题当模式串的前 j 个字符已匹配成功、第 j1 个字符失配时可以从哪继续答案是回退到lps[j-1]位置——即最长公共前后缀处。第二步KMP 如何用 LPS 表跳过匹配匹配阶段只用两个指针i指向主文、j指向模式串。三条规则对应源码中的三分支逻辑字符相等i、j同时前进一步j 达到模式串长度 M记录命中位置i - j然后j lps[j-1]继续找下一处命中字符失配j ! 0时j lps[j-1]主文指针不回退j 0时i前进一位关键在于规则 3失配时只移动模式串指针主文指针i永不后退。以文本AABAACAADAABABBBAABAA为例当主文走到AC...时时刻主文[i]模式[j]动作已匹配 AAB 后CB失配j lps[2] 0重试CA失配j0 → i 前进下一位AA重新对齐继续暴力匹配在这一步要把模式串整体右移重比 3 个字符KMP 直接利用 LPS 表一步到位。第三步跑通完整匹配验证命中位置运行Algorithms/Recursion-DP-Others/KMPMatching.php输出Pattern found at index : 0 Pattern found at index : 9对照原文本验证A A B A A C A A D A A B A B B B A A B A A 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 └AABA┘ └AABA┘ 命中0 命中9两处命中AABA的位置下标 0 和 9被准确找出且算法只需一次正向扫描即可完成。KMP 复杂度对比一眼看懂快多少算法时间复杂度空间复杂度失配代价朴素匹配PatternMatching.phpO(N×M)O(1)已比较字符全部重来KMPKMPMatching.phpO(NM)O(M)借助 LPS 表直接跳转LPS 构建耗时 O(M)匹配扫描耗时 O(N)两者相加就是 O(NM)。对于模式串较长、主文极长的场景日志检索、病毒特征码扫描、DNA 序列比对优势是数量级的。延伸阅读仓库中更多模式匹配相关实现仓库Algorithms/Recursion-DP-Others/目录下还有几个值得对照学习的文件Algorithms/Recursion-DP-Others/PatternMatching.php—— 朴素模式匹配KMP 的对照组Algorithms/Recursion-DP-Others/DNASequencing.php—— Needleman-Wunsch 序列比对KMP 思想在生物信息中的近亲应用Algorithms/Recursion-DP-Others/LCS.php—— 最长公共子序列理解利用重叠信息加速的另一典型案例配合仓库 README 中的 Dynamic Programming and Others 章节可以把 KMP、朴素匹配、序列比对放在一起对比学习快速建立对整类字符串算法的完整认知。总结KMP 之所以被称为字符串匹配的终极武器秘密全在 LPS 表——一次 O(M) 的预处理换来了主文指针永不回退的 O(NM) 总复杂度。动手把AABA的 LPS 表[0,1,0,1]画一遍、再把上表的匹配轨迹走一遍你就真正掌握了它。【免费下载链接】PHP-Data-Structure-and-AlgorithmsA repository with implementations of different data structures and algorithms using PHP项目地址: https://gitcode.com/gh_mirrors/ph/PHP-Data-Structure-and-Algorithms创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考