图解+原理推导完全读懂KPM算法

建站1310 更新时间：2025-06-08 05:44:35

图解+原理推导完全读懂KPM算法

文章目录

串定长顺序存储方式
串的模式匹配
- BF算法
- KMP算法
- - KMP算法原理
  - KMP算法实现
  - 求模式串T的next值算法
- 时间复杂度分析
- - BF算法分析
  - KMP算法分析
  - KMP算法与BF算法比较

串定长顺序存储方式

我们显式地在串的索引为0处存储串长。

#define MAXSTRLEN 255   // 用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN＋1]; //0号单元存放串的长度

串的模式匹配

模式匹配：设有主串S和子串T，子串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。
通常也把主串S称为目标串，把子串T称为模式串。
模式匹配成功是指在目标串S中找到一个模式串T是S的子串，返回T在S中的位置。
模式匹配不成功则指目标串S中不存在模式串T不是S的子串，返回-1。

BF算法

又称简单的、朴素的、穷举的模式匹配算法。算法的思路是
将主串的第 i 个字符和模式的第一个字符比较，

若相等，继续逐个比较后续字符；直到主串的一个连续子串字符序列与模式相等。返回值为主串中模式串匹配的子序列第一个字符的序号，即匹配成功。
若不等，从主串的下一字符起，重新与模式的第一个字符比较。

int Index_BF( SString S, SString T )
{// 返回模式串T在主串S中的位置。若不存在，则返回0。T非空int i = 1，j = 1;while ( i <= S[0] && j <= T[0] ) {if ( S[i] == T[j] ) {++i;++j;} // 继续比较后续字符else {i = i - j + 2;j = 1;} // 指针回溯重新开始下一趟匹配}if(j>T[0]) return i-T[0]; //返回匹配成功时主串对应的第一个字符的下标else return 0; //模式匹配不成功
} // Index_BF

时间复杂度：若主串s长度为n，模式串t长度为m
最好情况下的时间复杂度为O(m)。
算法在字符比较不相等，需要回溯（即i=i-j+1）：即退到s中的下一个字符开始进行继续匹配。
最坏情况下每趟比较m次，进行 n － m ＋ 1 n－m＋1 n－m＋1趟匹配，总比较次数为 m ( n − m + 1 ) m(n-m+1) m(n−m+1)，时间复杂度为 O ( n × m ) O(n×m) O(n×m)。

KMP算法

KMP算法原理

KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表，KMP算法又称克努特-莫里斯-普拉特操作。KMP算法的设计思想：当出现不匹配时，利用已经比较过的已知内容，来避免将主串指针回退到已比较的字符之前。

实现KMP算法需要解决的问题：

为什么主串的“指针”：i可以不回溯？
若某趟在 S i S_i Si和 T j T_j Tj“失配”时，
T 1 ∼ T j − 1 = S i − j + 1 ∼ S i − 1 T _{1} \sim T _{ j -1}= S _{ i - j +1} \sim S _{ i -1} T1∼Tj−1=Si−j+1∼Si−1
主串的切片 S i − j + 1 ∼ S i − 1 S _{ i - j +1} \sim S _{ i -1} Si−j+1∼Si−1的后缀中是否有能成功匹配的前缀，仅和 T 1 ∼ T j − 1 T _{1} \sim T _{ j -1} T1∼Tj−1的性质有关，可以在匹配算法之前预计算出来。
若某趟在 S i S_i Si和 T j T_j Tj“失配”时，主串中i不回溯，下一步进行 S i S_i Si与 T k T_k Tk的比较，那么k如何求出？
S i − k + 1 ∼ S i − 1 S _{ i - k +1} \sim S _{ i -1} Si−k+1∼Si−1的后缀必须是T的前缀：
T 1 ∼ T k − 1 = S i − k + 1 ∼ S i − 1 T _{1} \sim T _{ k -1}= S _{ i - k +1} \sim S _{ i -1} T1∼Tk−1=Si−k+1∼Si−1
S i − k + 1 ∼ S i − 1 S _{ i - k +1} \sim S _{ i -1} Si−k+1∼Si−1在上一步已经与T匹配的部分：
T j − k + 1 ∼ T j − 1 = S i − k + 1 ∼ S i − 1 T _{ j - k +1} \sim T _{ j -1}= S _{ i - k +1} \sim S _{ i -1} Tj−k+1∼Tj−1=Si−k+1∼Si−1
联立得：
T 1 ∼ T k − 1 = T j − k + 1 ∼ T j − 1 T _{1} \sim T _{ k -1}= T _{ j - k +1} \sim T _{ j -1} T1∼Tk−1=Tj−k+1∼Tj−1
k的解集为 K = { k ∣ k = 2 , 3 , . . . , j − 1 且 T 1 ∼ T k − 1 = T j − k + 1 ∼ T j − 1 } K=\{ k \mid k=2,3,...,j-1 \text { 且 }T _{1} \sim T _{ k -1}= T _{ j - k +1} \sim T _{ j -1} \} K={k∣k=2,3,...,j−1 且 T1∼Tk−1=Tj−k+1∼Tj−1}
k越大，模式串滑动的距离越小，为了避免遗漏选取k的最大值 k = max ⁡ K k=\max K k=maxK

模式中的前k-1个字符（最大真前缀）与模式中 T j T_j Tj字符前面的k-1个字符（最大真后缀）相等时，模式T就可以向右"滑动"至使 T k T_k Tk和 S i S_i Si对准，继续向右进行比较即可。

滑动位置k仅与模式串T有关。
因此可以预先为模式串设定一个next数组，若令next[j]=k，则next[j]表明当模式串中的第j个字符与主串中相应字符“失配”时，模式串中需要重新和主串中该字符进行比较的字符的位置。
n e x t [ j ] = { 0 , 当 j = 1 时 k = max ⁡ K , 当 j ≥ 2 , k ≠ ∅ 1 , 当 j ≥ 2 , k = ∅ next[j]=\left\{\begin{array}{ll}0, & 当 j=1 时 \\ k=\max K, & 当 j\geq2, k\neq \varnothing \\ 1, & 当 j\geq2, k= \varnothing \end{array}\right. next[j]=⎩⎨⎧0,k=maxK,1,当j=1时当j≥2,k=∅当j≥2,k=∅
其中 K = { k ∣ k = 2 , 3 , . . . , j − 1 且 T 1 ∼ T k − 1 = T j − k + 1 ∼ T j − 1 } K=\{ k \mid k=2,3,...,j-1 \text { 且 }T _{1} \sim T _{ k -1}= T _{ j - k +1} \sim T _{ j -1} \} K={k∣k=2,3,...,j−1 且 T1∼Tk−1=Tj−k+1∼Tj−1}
next[1]=0 表示T[1]与S[i]失配，下一步进行T[1]与S[i+1]的比较。
next[j]=1 表示 S i − k + 1 ∼ S i − 1 S _{ i - k +1} \sim S _{ i -1} Si−k+1∼Si−1的后缀都不为T的前缀：下一步进行T[1]与S[i]的比较。

KMP算法实现

int Index_KMP(SString S, SString T, int pos, int next[])
{// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
// 其中，T非空，1≤pos≤StrLength(S)。int i = pos, j = 1;while ( i<=S[0] && j<=T[0] ){  if ( j==0 || S[i]==T[j] ){++i; ++j; } // 继续比较后继字符else j=next[j]; // 模式串向右移动}if(j > T[0]) return i-T[0]; // 匹配成功，返回匹配模式串的首字符下标else return 0; //匹配失败
} // Index_KMP

求模式串T的next值算法

显然，next[1]=0， next[2]=1
如果next[j] =k，表明有 T 1 ∼ T k − 1 = T j − k + 1 ∼ T j − 1 T _{1} \sim T _{ k -1}= T _{ j - k +1} \sim T _{ j -1} T1∼Tk−1=Tj−k+1∼Tj−1，此时next[j+1]可能有两种情况：
(1). T k = T j T_k=T_j Tk=Tj，则 T 1 ∼ T k = T j − k + 1 ∼ T j T _{1} \sim T _{ k }= T _{ j - k +1} \sim T _{ j } T1∼Tk=Tj−k+1∼Tj，因此next[j+1]=next[j]+1=k＋1；
(2). T k ≠ T j T_k\neq T_j Tk=Tj，则相当于在模式串 T 1 ∼ T k T _{1} \sim T _{ k } T1∼Tk与主串 T T T的模式匹配问题中k于j失配，设 k ′ = n e x t [ k ] k'=next[k] k′=next[k]，
若 k ′ ≥ 2 k'\geq 2 k′≥2，则有 T 1 ∼ T k ′ − 1 = T j − k ′ + 1 ∼ T j − 1 T _{1} \sim T _{ k' -1}= T _{ j - k' +1} \sim T _{ j -1} T1∼Tk′−1=Tj−k′+1∼Tj−1，将k’赋给k并返回步骤2. ；
否则说明 T j − k + 1 ∼ T j − 1 T _{ j - k +1} \sim T _{ j -1} Tj−k+1∼Tj−1的真后缀中没有 T 1 ∼ T k T _{1} \sim T _{ k } T1∼Tk的前缀，则next[j+1]=1

void get_next( SString T, int &next[] )
{// 求模式串T的next函数值并存入数组nextint i = 1, k = 0; next[1] = 0; while ( i < T[0] ) {	if ( k == 0 || T[i] == T[k] )    {  ++i;++k;     next[i] = k;     }else k = next[k];}
} // get_next

时间复杂度分析

BF算法分析

最好情况下的时间复杂度为 O ( m ) O(m) O(m)。
算法在字符比较不相等，需要回溯（即i=i-j+1）：即退到s中的下一个字符开始进行继续匹配。
最坏情况下每趟比较m次，进行n－m＋1趟匹配，总比较次数为m(n-m+1)，时间复杂度为 O ( n × m ) O(n×m) O(n×m)。平均时间复杂度 O ( n × m ) O(n×m) O(n×m)

KMP算法分析

设串S的长度为n，串T长度为m，求next数组的时间复杂度为 O ( m ) O(m) O(m)，在后面的匹配中因主串S的下标不减即不回溯，比较次数可记为n，所以KMP算法平均时间复杂度为 O ( n + m ) O(n+m) O(n+m)。

KMP算法与BF算法比较

虽然朴素算法最坏时间复杂度为 O ( n × m ) O(n\times m) O(n×m)，但一般情况下，其实际执行时间近似于 O ( n + m ) O(n+m) O(n+m)，故仍被采用。
KMP算法仅当模式与主串存在许多“部分匹配”时才比朴素算法快得多。
KMP算法的最大特点是指示主串的指针i不需要回溯，这对处理从外设输入的庞大文件很有效，可以边读入边匹配而无需回头重读。