一、引言在字符串匹配问题中我们常需要在一个主串haystack中查找模式串needle的出现位置。传统的暴力匹配算法逐字符比较时间复杂度为 O(n×m)在面对较长文本时效率较低。KMPKnuth-Morris-Pratt算法通过巧妙利用模式串自身的信息——前缀表next 数组在匹配失败时避免主串指针回溯将时间复杂度优化到 O(nm)大幅提升匹配效率。本文将从题目出发通过原理讲解和代码分析带你深入理解 KMP 算法的核心思想。二、题目描述给你两个字符串haystack和needle请你在haystack字符串中找出needle字符串的第一个匹配项的下标下标从 0 开始。如果needle不是haystack的一部分则返回-1。这是力扣上的一道简单字符串匹配题目虽然标注为简单却可以帮助我们更好地理解 KMP 算法的设计思想。三、暴力匹配解法回顾在介绍 KMP 之前我们先看一下暴力匹配的实现。其思路非常直观从主串的每个位置开始逐一与模式串比较匹配失败则主串指针回溯到下一个起始位置重新开始比较。以下是暴力匹配的 Java 实现暴力匹配的最坏时间复杂度为 O(n×m)。当模式串较长且与主串有大量部分匹配时主串指针i会频繁回溯造成大量重复比较。KMP 算法的核心改进正是消除这种不必要的回溯。四、KMP算法核心思想KMP 算法的精妙之处在于前缀表next 数组的构建。前缀表记录了模式串中每个位置之前的子串中最长相等前后缀的长度。当匹配失败时我们可以根据 next 数组直接跳过已经匹配过的部分让模式串指针j回退到合适的位置而主串指针i完全不需要回溯。具体来说next 数组的含义是next[i]表示模式串中前i个字符组成的子串中最长相等前后缀的长度。在代码实现中我们通常让下标从 1 开始计算在字符串前加一个空格这样 next 数组的下标与字符位置一一对应。构建 next 数组的过程本身也利用了 KMP 的思想——在计算 next[i] 时如果当前字符不匹配j会通过next[j]进行回退这也是 KMP 算法自洽性的体现。KMP 匹配过程流程图图中可以看出KMP 匹配过程的核心特点主串指针i始终单向递增从不回溯模式串指针j在失配时通过next[j]智能跳转避免了暴力匹配中大量的无效重复比较。next 数组构建流程图从构建流程中可以清晰看到next 数组的计算本身就是 KMP 思想的自我应用当newndle[i] ! newndle[j1]时j通过next[j]回退这恰好复现了匹配失败时的跳转逻辑。五、KMP代码实现与解析以下是完整的 KMP 算法 Java 实现包含前缀表构建和匹配过程两部分关键代码解析下标从1开始在字符串前添加空格使下标与自然计数对齐next[1] 默认为 0逻辑更清晰。next 数组构建i从 2 开始遍历模式串j表示当前最长相等前后缀的长度。当newndle[i] ! newndle[j1]时j通过next[j]回退这正是 KMP 思想在构建阶段的自我应用。匹配过程主串指针i从 1 到 n 单向前进永不回溯模式串指针j在不匹配时通过 next 数组智能跳转。当j m时表示完全匹配返回i - m即为模式串在主串中的起始下标。六、总结KMP 算法的核心在于通过前缀表next 数组记录模式串的自我匹配信息从而在主串匹配失败时避免指针回溯将时间复杂度从 O(n×m) 优化到 O(nm)。理解 next 数组的构建过程是掌握 KMP 的关键——它本身也是 KMP 思想的一次精彩实践。建议读者在理解原理后亲手默写一遍代码尤其注意j next[j]这一回退逻辑它正是 KMP 算法画龙点睛之笔。