1
4.４ 串的模式匹配算法
一、基本概念
1、模式匹配（定位）
设有主串 S和子串 T（将 S称为目标串，将 T称为模式
串），在主串 S中，从位置 start开始查找，如若在主
串 S中找到一个与子串 T相等的子串，则返回 T的第一
个字符在主串中的位置，否则返回 -1。
2、算法目的
确定主串中所含子串第一次出现的位置 （ 定位 ）
3、算法种类
BF算法 （又称古典的、经典的、朴素的、穷举的）
KMP算法
2
二,Brute-Force算法
1,Brute-Force算法的设计思想：
? 将主串 S的第一个字符和模式 T的第 1个字符比较，
若 相等,继续逐个比较后续字符；
若 不等,从主串 S的下一字符起，重新与 T第一个字符比较。
? 直到主串 S的一个连续子串字符序列与模式 T相等。返回值为 S
中与 T匹配的子序列 第一个字符的序号,即匹配成功。
否则，匹配失败，返回值 –1。
2,Brute-Force算法的实现
typedef struct
{ char str[MaxSize];
int length;
}String;
3
int BFIndex(String S,int start,String T)
{ int i = start,j = 0,v;
while(i < S.length && j < T.length)
{ if(S.str[i] == T.str[j]) {i++; j++; }
else{ i = i-j+1; j = 0; }
}
if (j==T.length) v=i-T.length;
else v=-1;
return v;
}
4
3,BF算法 的时间复杂度
讨论：
若 n为主串长度,m为子串长度，则串的 BF匹配算法最坏的情况
下需要比较字符的总次数为 (n-m+1)*m＝ O(n*m)
最好的情况是,一配就中！ 只比较了 m次。
最恶劣情况是,主串前面 n-m个位置都 部分匹配 到子串的最后一
位，即这 n-m位比较了 m次，别忘了最后 m位也各比较了一次，
还要加上 m！所以总次数为,(n-m)*m+m ＝ (n-m+1)*m
能否利用已 部分匹配过 的信息而加快模式串的滑动速度？
能！ 而且主串 S的指针 i不必回溯 ！最坏情况也能达到 O(n+m)
请看 KMP算法！
5
尽量利用已经 部分匹配 的结果信息，尽量让 i不要回溯，加快
模式串的滑动速度。
例：
三,KMP算法
１,KMP算法设计思想：
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
需要讨论两个问题：
①如何由 当前部分匹配结果 确定模式向右滑动的新比较起点 k？
② 模式应该向右滑多远才是高效率的?
ii
i
k
kk
ii
6奇妙的结果,k 仅与模式串 T有关！
请抓住部分匹配时的两个特征：
两式联立可得：, T0…T k-1‖=?Tj-k …T j-1‘
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
i
k
则 T的 k-1～０ ＝ S前 i-1～ i-k)位
设目前打算与 T的第 k字符开始比较
(1)
(2)
?T０ … Tk-1‘
则 T的 j-1～ j-k位 ＝ S前 i-1～ i-k)位
i
k j
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
刚才肯定是在 S的 i处和 T的第 j字符 处失配
?Tj-k…T j-1‘ 截取一段，但 k有限制,0<k<j
k是追求的新起点
注意,j 为当前已知的失配位置，我们的目标是计算新起点 k。
式中仅剩一个未知数 k，理论上已可解！
7
根据模式串 T的规律：, T0…T k-1‖=―Tj-k…T j-1‖
由当前失配位置 j(已知 ),可以 归纳 计算新起点 k的表达式。
next[ j ]＝
-1 当 j＝ 0时
max { k | 0<k<j 且‘ T0…T k-1‘=?Tj-k…T j-1‘}
0 其他情况
注意：
（ 1） k值仅取决于模式串本身而与相匹配的主串无关。
（ 2） k值为模式串从头向后及从 j向前的两部分的最大相同子串
的长度。
（ 3）这里的两部分子串可以有部分重叠的字符，但不可以全部
重叠。
令 k = next[ j ]（ k 与 j 显然具有函数关系），则
取 T首与 Tj处最大的相同子串
新起点 k怎么求？
8
next[j]函数表征着模式 T中最大相同前缀子串和后缀子串
（真子串）的长度。
可见，模式中 相似部分越多，则 next[j]函数越大,它既
表示 模式 T字符之间的相关度越高，也表示 j位置以前与主串 部
分匹配 的字符数越多。
即,next[j]越大，模式串向右滑动得越远,与主串进行
比较的次数越少，时间复杂度就越低（时间效率）。
再想一想：如果主串是外存中一个
大文件，用 KMP算法效果又如何？
9
从两头往中间比较
例,模 式 串 T,a b a a b c a c
可能失配位 j,0 1 2 3 4 5 6 7
新匹配位 k=next[j],
next[ j ]＝
0 当 j＝ 1时
max { k |1<k<j 且‘ T1…T k-1‘=?Tj-(k-1) …T j-1‘ }
1 其他情况
-1 0 0 1 1 2 0 1
讨论：
j=0时,next[ j ]≡ -1； //属于,j=1‖情况 ;
j=1时,next[ j ]≡ 0； // 找不到 0<k<j的 k，属于“其他情况”；
j=2时,next[ j ]≡ 0； //只需查看‘ T0‘=?T1‘成立否
j=3时,next[ j ]≡ 1； //要查看 ‘ T0‘=?T2‘ 及 ‘ T0T1‘=?T1T2‘ 是否成立
j=4时,next[ j ]≡ 1； //要查看‘ T0‘=?T3‘,‘ T0T1‘=?T2T3‘ 和
‘ T0T1T2‘=?T1T2T3‘是否成立
刚才已归纳：
以此类推，可得后续 next[j]值。
next[j]与 s无关，
可以预先计算
怎样计算模式 T所有可能的失配点 j 所对应的 next[j]？
10
下一个要讨论的问题是：如何 用递推方式 来求出最大相
同子串的长度呢？这个问题一旦解决，整个 KMP算法就可以
掌握得很透彻了。
求子串 next[i]值的算法：
void GetNext(String T,int next[])
{ int j = 0,k = 0;
next[0] = -1;
while(j < T.length){
if(T.str[j]==T.str[k])
{ next[j+1]=k+1; j++; k++; }
else if (k==0){ next[j+1]=0; j++; }
else k=next[k];
}
}
11
KMP算法的思想
设 s为主串,t为模式串，设 i为主串 s当前比较字
符的下标,j为模式串 t当前比较字符的下标，令 i和
j的初值为０。当 si = tj时,i和 j分别增 1再继续比
较；否则 i不变,j改变为 next[j]值 （即模式串右
滑）后再继续比较。依次类推，直到出现下列两种
情况之一：一是 j退回到某个 j=next[j]值时有 si =
tj,则 i和 j分别增 1后再继续比较；二是 j退回到
j=-1时，令主串和子串的下标各增 1，随后比较 si+1
和 t0 。这样的循环过程一直进行到变量大于等于
S.length或变量 j大于等于 T.length时为止。
12
第一步，先把模式 T所有可能的失配点 j 所对应的 next[j]计算 出来；
第二步：执行定位函数 Index_kmp （与 BF算法模块非常相似）
KMP算法的实现
int KMPIndex(String S,int start,String T,int next[ ])
{int i=start,j=0,v;
while ( i<=S.length && j<T.length ) {
if (j==-1|| S.str[i] = = T.str[j] ) {i++; j++ } //不失配则继续比
较后续字符
else j=next[j]; //特点,S的 i指针不回溯，而且从 T的 k位置开始匹
配
}
if(j==T.length) v=I-T.length;
else v=-1;
return v;
}
13
主函数
void main(void)
{ String S = {{"cddcdc"},6},T = {{"cdc"},3};
int next[8],pos;
GetNext(T,next);
pos = KMPIndex(S,0,T,next);
printf("pos = %d\n",pos);
}
14
2,KMP算法的 时间复杂度
注意,由于 BF算法在一般情况下的时间复杂度也近似于
O(n+m)，所以至今仍被广泛采用。
而此时 KMP的情况是,由于指针 i无须回溯，比较次数仅为 n,
即使加上计算 next[j]时所用的比较次数 m，比较总次数也仅
为 n+m=O(n＋ m),大大快于 BF算法。
回顾 BF的最恶劣情况,S与 T之间存在大量的 部分匹配,比较
总次数为,(n-m+1)*m＝ O(n*m)
因为主串指针 i不必回溯，所以从外存输入文件时可以做
到边读入边查找 ——―流水作业, ！
KMP算法的用途：
第 4章小结
串
s =―a1a2 ……..a n‖
定长顺序存储结构
块链存储结构
堆存储结构
逻辑结构
存储结构
操作 (或运算 )
模式匹配算法
若干函数的实现
模式匹配 即 子串定位运算,即如何实现 Index(S,T,pos)函数
BF算法 ———古典
KMP算法 ——快速（用 next[j]或 nextval[j])
本章结束
4.４ 串的模式匹配算法
一、基本概念
1、模式匹配（定位）
设有主串 S和子串 T（将 S称为目标串，将 T称为模式
串），在主串 S中，从位置 start开始查找，如若在主
串 S中找到一个与子串 T相等的子串，则返回 T的第一
个字符在主串中的位置，否则返回 -1。
2、算法目的
确定主串中所含子串第一次出现的位置 （ 定位 ）
3、算法种类
BF算法 （又称古典的、经典的、朴素的、穷举的）
KMP算法
2
二,Brute-Force算法
1,Brute-Force算法的设计思想：
? 将主串 S的第一个字符和模式 T的第 1个字符比较，
若 相等,继续逐个比较后续字符；
若 不等,从主串 S的下一字符起，重新与 T第一个字符比较。
? 直到主串 S的一个连续子串字符序列与模式 T相等。返回值为 S
中与 T匹配的子序列 第一个字符的序号,即匹配成功。
否则，匹配失败，返回值 –1。
2,Brute-Force算法的实现
typedef struct
{ char str[MaxSize];
int length;
}String;
3
int BFIndex(String S,int start,String T)
{ int i = start,j = 0,v;
while(i < S.length && j < T.length)
{ if(S.str[i] == T.str[j]) {i++; j++; }
else{ i = i-j+1; j = 0; }
}
if (j==T.length) v=i-T.length;
else v=-1;
return v;
}
4
3,BF算法 的时间复杂度
讨论：
若 n为主串长度,m为子串长度，则串的 BF匹配算法最坏的情况
下需要比较字符的总次数为 (n-m+1)*m＝ O(n*m)
最好的情况是,一配就中！ 只比较了 m次。
最恶劣情况是,主串前面 n-m个位置都 部分匹配 到子串的最后一
位，即这 n-m位比较了 m次，别忘了最后 m位也各比较了一次，
还要加上 m！所以总次数为,(n-m)*m+m ＝ (n-m+1)*m
能否利用已 部分匹配过 的信息而加快模式串的滑动速度？
能！ 而且主串 S的指针 i不必回溯 ！最坏情况也能达到 O(n+m)
请看 KMP算法！
5
尽量利用已经 部分匹配 的结果信息，尽量让 i不要回溯，加快
模式串的滑动速度。
例：
三,KMP算法
１,KMP算法设计思想：
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
需要讨论两个问题：
①如何由 当前部分匹配结果 确定模式向右滑动的新比较起点 k？
② 模式应该向右滑多远才是高效率的?
ii
i
k
kk
ii
6奇妙的结果,k 仅与模式串 T有关！
请抓住部分匹配时的两个特征：
两式联立可得：, T0…T k-1‖=?Tj-k …T j-1‘
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
i
k
则 T的 k-1～０ ＝ S前 i-1～ i-k)位
设目前打算与 T的第 k字符开始比较
(1)
(2)
?T０ … Tk-1‘
则 T的 j-1～ j-k位 ＝ S前 i-1～ i-k)位
i
k j
S=?a b a b c a b c a c b a b‘
T=?a b c a c‘
刚才肯定是在 S的 i处和 T的第 j字符 处失配
?Tj-k…T j-1‘ 截取一段，但 k有限制,0<k<j
k是追求的新起点
注意,j 为当前已知的失配位置，我们的目标是计算新起点 k。
式中仅剩一个未知数 k，理论上已可解！
7
根据模式串 T的规律：, T0…T k-1‖=―Tj-k…T j-1‖
由当前失配位置 j(已知 ),可以 归纳 计算新起点 k的表达式。
next[ j ]＝
-1 当 j＝ 0时
max { k | 0<k<j 且‘ T0…T k-1‘=?Tj-k…T j-1‘}
0 其他情况
注意：
（ 1） k值仅取决于模式串本身而与相匹配的主串无关。
（ 2） k值为模式串从头向后及从 j向前的两部分的最大相同子串
的长度。
（ 3）这里的两部分子串可以有部分重叠的字符，但不可以全部
重叠。
令 k = next[ j ]（ k 与 j 显然具有函数关系），则
取 T首与 Tj处最大的相同子串
新起点 k怎么求？
8
next[j]函数表征着模式 T中最大相同前缀子串和后缀子串
（真子串）的长度。
可见，模式中 相似部分越多，则 next[j]函数越大,它既
表示 模式 T字符之间的相关度越高，也表示 j位置以前与主串 部
分匹配 的字符数越多。
即,next[j]越大，模式串向右滑动得越远,与主串进行
比较的次数越少，时间复杂度就越低（时间效率）。
再想一想：如果主串是外存中一个
大文件，用 KMP算法效果又如何？
9
从两头往中间比较
例,模 式 串 T,a b a a b c a c
可能失配位 j,0 1 2 3 4 5 6 7
新匹配位 k=next[j],
next[ j ]＝
0 当 j＝ 1时
max { k |1<k<j 且‘ T1…T k-1‘=?Tj-(k-1) …T j-1‘ }
1 其他情况
-1 0 0 1 1 2 0 1
讨论：
j=0时,next[ j ]≡ -1； //属于,j=1‖情况 ;
j=1时,next[ j ]≡ 0； // 找不到 0<k<j的 k，属于“其他情况”；
j=2时,next[ j ]≡ 0； //只需查看‘ T0‘=?T1‘成立否
j=3时,next[ j ]≡ 1； //要查看 ‘ T0‘=?T2‘ 及 ‘ T0T1‘=?T1T2‘ 是否成立
j=4时,next[ j ]≡ 1； //要查看‘ T0‘=?T3‘,‘ T0T1‘=?T2T3‘ 和
‘ T0T1T2‘=?T1T2T3‘是否成立
刚才已归纳：
以此类推，可得后续 next[j]值。
next[j]与 s无关，
可以预先计算
怎样计算模式 T所有可能的失配点 j 所对应的 next[j]？
10
下一个要讨论的问题是：如何 用递推方式 来求出最大相
同子串的长度呢？这个问题一旦解决，整个 KMP算法就可以
掌握得很透彻了。
求子串 next[i]值的算法：
void GetNext(String T,int next[])
{ int j = 0,k = 0;
next[0] = -1;
while(j < T.length){
if(T.str[j]==T.str[k])
{ next[j+1]=k+1; j++; k++; }
else if (k==0){ next[j+1]=0; j++; }
else k=next[k];
}
}
11
KMP算法的思想
设 s为主串,t为模式串，设 i为主串 s当前比较字
符的下标,j为模式串 t当前比较字符的下标，令 i和
j的初值为０。当 si = tj时,i和 j分别增 1再继续比
较；否则 i不变,j改变为 next[j]值 （即模式串右
滑）后再继续比较。依次类推，直到出现下列两种
情况之一：一是 j退回到某个 j=next[j]值时有 si =
tj,则 i和 j分别增 1后再继续比较；二是 j退回到
j=-1时，令主串和子串的下标各增 1，随后比较 si+1
和 t0 。这样的循环过程一直进行到变量大于等于
S.length或变量 j大于等于 T.length时为止。
12
第一步，先把模式 T所有可能的失配点 j 所对应的 next[j]计算 出来；
第二步：执行定位函数 Index_kmp （与 BF算法模块非常相似）
KMP算法的实现
int KMPIndex(String S,int start,String T,int next[ ])
{int i=start,j=0,v;
while ( i<=S.length && j<T.length ) {
if (j==-1|| S.str[i] = = T.str[j] ) {i++; j++ } //不失配则继续比
较后续字符
else j=next[j]; //特点,S的 i指针不回溯，而且从 T的 k位置开始匹
配
}
if(j==T.length) v=I-T.length;
else v=-1;
return v;
}
13
主函数
void main(void)
{ String S = {{"cddcdc"},6},T = {{"cdc"},3};
int next[8],pos;
GetNext(T,next);
pos = KMPIndex(S,0,T,next);
printf("pos = %d\n",pos);
}
14
2,KMP算法的 时间复杂度
注意,由于 BF算法在一般情况下的时间复杂度也近似于
O(n+m)，所以至今仍被广泛采用。
而此时 KMP的情况是,由于指针 i无须回溯，比较次数仅为 n,
即使加上计算 next[j]时所用的比较次数 m，比较总次数也仅
为 n+m=O(n＋ m),大大快于 BF算法。
回顾 BF的最恶劣情况,S与 T之间存在大量的 部分匹配,比较
总次数为,(n-m+1)*m＝ O(n*m)
因为主串指针 i不必回溯，所以从外存输入文件时可以做
到边读入边查找 ——―流水作业, ！
KMP算法的用途：
第 4章小结
串
s =―a1a2 ……..a n‖
定长顺序存储结构
块链存储结构
堆存储结构
逻辑结构
存储结构
操作 (或运算 )
模式匹配算法
若干函数的实现
模式匹配 即 子串定位运算,即如何实现 Index(S,T,pos)函数
BF算法 ———古典
KMP算法 ——快速（用 next[j]或 nextval[j])
本章结束
