KMP字符串匹配算法原理与实现 一、问题描述 字符串匹配是计算机科学中的基础问题，即在一个主串（文本）中查找一个子串（模式）的出现位置。暴力匹配算法（逐字符比较）的时间复杂度为O(mn)，其中m为模式串长度，n为主串长度。KMP算法通过预处理模式串，利用匹配失败时的已匹配信息避免回溯，将时间复杂度优化至O(m+n)。 二、核心思想：部分匹配表（Next数组） 前缀与后缀的定义 前缀：除最后一个字符外，字符串的所有头部子串。 后缀：除第一个字符外，字符串的所有尾部子串。 示例 ：对于字符串"ABABA"： 前缀：A, AB, ABA, ABAB 后缀：BABA, ABA, BA, A 最长公共前后缀长度 对模式串的每个子串P[ 0:i ]（i从0到m-1），计算其最长相等前缀和后缀的长度。 示例 ：模式串"ABABC"： P[ 0:0 ]="A"：长度为0（无前后缀） P[ 0:1]="AB"：前缀[ A]，后缀[ B ]，无公共部分 → 长度0 P[ 0:2]="ABA"：前缀[ A, AB]，后缀[ BA, A ] → 公共后缀"A"长度1 P[ 0:3]="ABAB"：前缀[ A, AB, ABA]，后缀[ BAB, AB, B ] → 公共后缀"AB"长度2 P[ 0:4 ]="ABABC"：无公共前后缀 → 长度0 Next数组构建 Next数组存储每个位置匹配失败时，模式串应跳转的位置。定义Next[ i]为P[ 0:i ]的最长公共前后缀长度。 示例 ：模式串"ABABC"的Next数组： | i | 子串 | Next[ i ] | |-----|--------|---------| | 0 | A | 0 | | 1 | AB | 0 | | 2 | ABA | 1 | | 3 | ABAB | 2 | | 4 | ABABC | 0 | 三、Next数组的代码实现 初始化Next[ 0 ]=0，指针i=1（当前子串末尾），j=0（已匹配前缀末尾）。 循环处理i从1到m-1： 若P[ i]==P[ j]，则Next[ i ]=j+1，i和j同时右移； 若P[ i]!=P[ j]且j>0，则j回退至Next[ j-1 ]； 若j=0且P[ i]!=P[ j]，则Next[ i ]=0，i右移。 示例 ：构建"ABABC"的Next数组过程： i=1, j=0: P[ 1]='B'≠P[ 0]='A'，j=0 → Next[ 1 ]=0, i=2 i=2, j=0: P[ 2]='A'=P[ 0] → Next[ 2 ]=1, i=3, j=1 i=3, j=1: P[ 3]='B'=P[ 1] → Next[ 3 ]=2, i=4, j=2 i=4, j=2: P[ 4]='C'≠P[ 2]='A'，j回退至Next[ 1]=0；P[ 4]≠P[ 0] → Next[ 4 ]=0 四、KMP匹配过程 初始化主串指针i=0，模式串指针j=0。 循环比较主串T[ i]和模式串P[ j ]： 若T[ i]==P[ j ]，则i和j同时右移； 若j=m（模式串完全匹配），记录位置i-m，并令j=Next[ j-1 ]继续匹配； 若T[ i]!=P[ j]且j>0，则j回退至Next[ j-1 ]； 若j=0且不匹配，则i右移。 示例 ：主串T="ABABABC"，模式串P="ABABC"： 首次匹配至T[ 4]='A'与P[ 4]='C'失败，j回退至Next[ 3 ]=2； 比较T[ 4]='A'与P[ 2 ]='A'，匹配成功，继续匹配后续字符。 五、算法优化（NextVal数组） 若回退后字符与原失败字符相同，可进一步优化跳转。 示例 ：模式串"AAAAB"的Next数组为[ 0,1,2,3,0]，但失败时连续回退效率低。优化后NextVal数组为[ 0,0,0,0,4 ]，直接跳至首位。 六、总结 KMP算法通过Next数组避免主串指针回溯，利用模式串的自相似性提升效率。关键点在于理解部分匹配表的物理意义：它记录了模式串自身的前后缀匹配信息，使得匹配失败时能智能跳转。