KMP算法（字符串匹配） 我将为您详细讲解KMP算法（Knuth-Morris-Pratt算法），这是一种高效的字符串匹配算法。 题目描述 给定一个文本串text和一个模式串pattern，在text中查找pattern第一次出现的位置。如果pattern在text中存在，返回起始索引；否则返回-1。 算法核心思想 KMP算法的核心是利用已经部分匹配的信息，通过预处理模式串构建一个"部分匹配表"（next数组），在匹配失败时能够跳过不必要的比较，将模式串向右移动多位而不是仅仅一位。 详细解题过程 第一步：理解暴力匹配的不足 暴力匹配算法的时间复杂度为O(m×n)，因为： 每次匹配失败时，文本串指针回退到上次起始的下一个位置 模式串指针回退到开头 造成大量重复比较 第二步：构建部分匹配表（next数组） 部分匹配表记录模式串每个位置的最长相同前后缀长度。 以模式串"ABABC"为例： 索引0："A" → 前后缀都为空 → next[ 0 ] = 0 索引1："AB" → 前缀[ "A"]，后缀[ "B"]，无相同 → next[ 1 ] = 0 索引2："ABA" → 前缀[ "A","AB"]，后缀[ "A","BA"]，相同"A" → next[ 2 ] = 1 索引3："ABAB" → 前缀[ "A","AB","ABA"]，后缀[ "B","AB","BAB"]，相同"AB" → next[ 3 ] = 2 索引4："ABABC" → 前缀[ "A","AB","ABA","ABAB"]，后缀[ "C","BC","ABC","BABC"]，无相同 → next[ 4 ] = 0 next数组：[ 0, 0, 1, 2, 0 ] 构建next数组的算法步骤： 初始化next[ 0 ] = 0，len = 0，i = 1 当i < pattern长度时： 如果pattern[ i] == pattern[ len]，则len++，next[ i ] = len，i++ 否则如果len > 0，回退len = next[ len-1 ] 否则next[ i ] = 0，i++ 第三步：KMP匹配过程 使用双指针i（文本串）和j（模式串）进行匹配： 初始化i = 0, j = 0 当i < text长度且j < pattern长度时： 如果text[ i] == pattern[ j ]，i++，j++ 否则如果j > 0，j = next[ j-1 ]（利用部分匹配表回退） 否则i++（模式串在开头就不匹配） 如果j == pattern长度，返回i - j（匹配成功） 否则返回-1（匹配失败） 完整示例 文本串："ABABDABACDABABC" 模式串："ABABC" next数组：[ 0, 0, 1, 2, 0 ] 匹配过程： i=0,j=0: A=A → i=1,j=1 i=1,j=1: B=B → i=2,j=2 i=2,j=2: A=A → i=3,j=3 i=3,j=3: B=B → i=4,j=4 i=4,j=4: D≠C → j=next[ 3 ]=2 i=4,j=2: D≠A → j=next[ 1 ]=0 i=4,j=0: D≠A → i=5 ...继续匹配直到找到完整模式串 算法优势 时间复杂度：O(m+n)，其中预处理O(n)，匹配O(m) 空间复杂度：O(n)用于存储next数组 避免文本串指针回退，提高匹配效率 KMP算法通过预处理模式串，在匹配失败时能够智能地移动模式串，避免了暴力算法中的大量重复比较，是字符串匹配问题的高效解决方案。