KMP字符串匹配算法 题目描述 KMP算法是一种高效的字符串匹配算法，用于在一个主文本字符串（text）中查找一个模式字符串（pattern）的出现位置。其核心思想是当出现不匹配时，利用已经匹配的部分信息，避免从头重新开始比较，从而将时间复杂度优化到O(n+m)，其中n是text长度，m是pattern长度。 解题过程 理解暴力匹配的不足 暴力匹配法：从text的每个位置开始，逐个字符与pattern比较。不匹配时，text的指针回退到本次起始位置的下一个字符。 缺点：时间复杂度O(n* m)，存在大量不必要的回退和重复比较。 KMP的核心思路：利用部分匹配信息 当pattern与text在某个位置不匹配时，我们已经知道了text中当前窗口内的部分字符。 KMP算法预先计算pattern自身的"部分匹配表"（也称next数组），记录匹配失败时pattern指针应该跳转的位置。 这样，text的指针无需回退，只需移动pattern指针，继续比较。 构建next数组（关键步骤） next数组定义：对于pattern[ 0..i]这个子串，其"最长相等真前缀和真后缀的长度"（不包括自身）就是next[ i ]的值。 真前缀：不包括最后一个字符的所有前缀；真后缀：不包括第一个字符的所有后缀。 计算过程（使用双指针法）： 初始化：next[ 0 ] = 0（单个字符无真前后缀），指针i=1（当前子串结尾），j=0（指向前缀的结尾，也代表当前匹配长度） 遍历i从1到m-1： 情况1：pattern[ i] == pattern[ j]，则j++，next[ i ] = j，i++ 情况2：不相等且j>0，则令j = next[ j-1 ]（回退j到前一个位置的最长前缀结尾） 情况3：不相等且j==0，则next[ i ] = 0，i++ 匹配过程 初始化：指针i=0（遍历text），j=0（遍历pattern） 遍历i从0到n-1： 当j>0且text[ i] != pattern[ j]时，j = next[ j-1 ]（利用next数组跳转） 当text[ i] == pattern[ j ]时，j++，i++ 如果j == m，表示找到匹配，记录位置i-m+1，然后j = next[ j-1 ]继续寻找 示例说明 以pattern="ababc"和text="abababc"为例： 构建next数组： "a": next[ 0 ]=0 "ab": 真前缀[ "a"]，真后缀[ "b"]，无公共，next[ 1 ]=0 "aba": 真前缀[ "a","ab"]，真后缀[ "ba","a"]，公共"a"长度1，next[ 2 ]=1 "abab": 真前缀[ "a","ab","aba"]，真后缀[ "bab","ab","b"]，公共"ab"长度2，next[ 3 ]=2 "ababc": 真前缀[ "a","ab","aba","abab"]，真后缀[ "babc","abc","bc","c"]，无公共，next[ 4 ]=0 next = [ 0,0,1,2,0 ] 匹配过程： text: a b a b a b c pat: a b a b c 前4个字符匹配，第5个字符text[ 4]='a'与pat[ 4 ]='c'不匹配 查next[ 3]=2，j跳转到2，继续比较text[ 4]与pat[ 2 ] 匹配成功，最终在位置2找到模式串