《数据结构》课程PPT教学课件（2012）第4章 串 String（2/2）

第4章串(String) 4.1串类型的定义 4.2串的表示和实现 4.3 串的模式匹配算法 7

1 第4章 串（String） 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法

4.3 串的模式匹配算法 算法目的： 确定主串中所含子串第一次出现的位置（定位） 定位问题称为串的模式匹配，典型函数为Index(S,T,pos) 算法种类： 。BF算法（又称古典的、经典的、朴素的、穷举的〉 KMP算法 带回溯，速度慢 避免回溯，匹配速度快， 是全课程的亮点之一

2 算法目的：确定主串中所含子串第一次出现的位置（定位） 4.3 串的模式匹配算法 • BF算法 （又称古典的、经典的、朴素的、穷举的） • KMP算法 算法种类： 带回溯，速度慢 避免回溯，匹配速度快， 是全课程的亮点之一 定位问题称为串的模式匹配，典型函数为Index(S,T,pos)

BF算法的实现一即编写Index(S,T,pos)函数 例1：S=‘ababcabcacbab',T=‘abcac',pos=1, 求：串T在串S中第pos个字符之后的位置。 BF算法设计思想： 将住串S的第pos个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串S的下一字符(pos+1)起， 重新与T第一个 字符比较。 直到主串$的一个连续子串字符序列与模式T相等。返回值为S 中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值0· 利用演示系统看BF算法执行过程

3 BF算法的实现—即编写Index(S, T, pos)函数 例1： S=‘ababcabcacbab’ ，T=‘abcac’ ，pos=1， 求：串T在串S中第pos个字符之后的位置。 利用演示系统看BF算法执行过程。 BF算法设计思想： • 将主串S的第pos个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串S的下一字符（pos+1）起，重新与T第一个 字符比较。 • 直到主串S的一个连续子串字符序列与模式T相等。返回值为S 中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0

BF算法的时间复杂度 讨论： 若为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下 需要比较字符的总次数为 (n-mt1)*m=0n*m) 最好的情况是：一配就中！只比较了m次。 最坏的情况是：主串前面-m个位置都部分匹配到子串的最后 一位，即这n-m位比较了m次，别忘了最后m位也各比较了一 次，还要加上m!所以总次数为：(-m)*m+m=(-m+1)*m 一般的情况是：O(m+m 推导方法：要从最好到最坏情况统计总的比较次数，然后取平 均。 能否加快子串（又称模式串）的滑动速度？ 能！利用已部分匹配过的信息使主串$的指针不必回溯，最 坏情况也能达到O(n+m) 清看KMP算法！

4 讨论： 若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下 需要比较字符的总次数为 (n-m+1)*m＝O(n*m) 一般的情况是：O(n+m) 推导方法：要从最好到最坏情况统计总的比较次数，然后取平 均。 BF算法的时间复杂度 最好的情况是：一配就中！ 只比较了m次。 能否加快子串（又称模式串）的滑动速度？ 能！利用已部分匹配过的信息使主串S的指针i不必回溯，最 坏情况也能达到O(n+m) 请看KMP算法！ 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后 一位，即这n-m位比较了m次，别忘了最后m位也各比较了一 次，还要加上m！所以总次数为：(n-m)*m+m ＝(n-m+1)*m

KMP算法（特点：速度快） KMP算法设计思想 ② KMP算法的推导过程 ③ KMP算法的实现 (关键技术：计算next[j]) ④ KMP算法的时间复杂度 全书一大亮点！

5 KMP算法（特点：速度快） ① KMP算法设计思想 ② KMP算法的推导过程 ③ KMP算法的实现 （关键技术:计算next[j]） ④ KMP算法的时间复杂度 全书一大亮点！

①KMP算法设计思想： (参见教材P80-84) 尽量利用已经部分匹配的结果信息，尽量让不要回溯，加快模式 串的滑动速度。 例：i S='a ba bc a bc a cb a b' S-'a babc a bc a c b a b' T=abc a c' T=abca c' S=a/babca bc a c b a b' i-T[O] Index_kmpl的返回值应为 i=6 需要讨论两个问题： ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k? ②模式应该向右滑多远才是高效率的？ 6

6 尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式 串的滑动速度。 例： ① KMP算法设计思想： (参见教材P80-84） 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’ Index_kmp的返回值应为 i=6 需要讨论两个问题： ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ ② 模式应该向右滑多远才是高效率的? i i i k k a b a a b c k i i i-T[0]

②KMP算法的推导过程： (见教材P81 k是追求的新起点 请抓住部分匹配时的两个特征： (1) S=a babc a b c a c b a b' 设目前打算与T的第k字符开始比较 T=‘a bc a c 则T的k-1~1位=S前i-1i-(k-1)位 即(42)式含义 T. (2) S=‘ababcbcacbab’刚才肯定是在s的处和r的第字符处失配 0c 则T的j-1j-(k-1)位S前i-1~i-k-1)位 即(4-3)式含义 TT’截取一段，但k有限制，1k 两式联立可得：TT’=T)Ti 加速的前提：T首与 Tj处有相同子串 注意：j为当前已知的失配位置，我们的目标是计算新起点k。 式中仅剩一个未知数k,理论上已可解！ 奇妙的结果：k仅与模式串T有关！

奇妙的结果： 7 k 仅与模式串T有关！ ② KMP算法的推导过程：（见教材P81） 请抓住部分匹配时的两个特征： 两式联立可得：‘T1.Tk-1 ’=‘Tj-(k-1) .Tj-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～1位＝S前i-1～i-(k-1)位 即(4-2）式含义 设目前打算与T的第k字符开始比较 (1) (2) ‘T1.Tk-1 ’ 则T的j-1～j-(k-1)位＝ S前i-1～i-(k-1)位 即(4-3）式含义 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-1) .Tj-1 ’ 截取一段，但k有限制，1<k<j k是追求的新起点 加速的前提：T首与 Tj处有相同子串 注意：j 为当前已知的失配位置，我们的目标是计算新起点 k。 式中仅剩一个未知数k，理论上已可解！

新起点k怎么求？ 根据模式串T的规律： TI.TK=Ti-(-1).TH 由当前失配位置（已知），可以归纳出计算新起点k的表达式。 令k=next[j】(k与j显然具有函数关系)，则 0 当j=1时 不比较 next[jl目 max k1<k<j T1.TkTi-(K-1).Ti' 其他情况 取T首与T处最大的相同子串 讨论： (1) next[jl的物理意义是什么？ (2) next[j]具体怎么求？一即KMP算法的实现

8 根据模式串T的规律： ‘T1.Tk-1 ’=‘Tj-(k-1) .Tj-1 ’ 由当前失配位置j(已知) ，可以归纳出计算新起点 k的表达式。 next[ j ]＝ 0 当j＝1时 //不比较 max { k | 1<k<j 且‘T1.Tk-1 ’=‘Tj-(k-1) .Tj-1 ’ } 1 其他情况 讨论： （1） next[ j ]的物理意义是什么？ （2） next[ j ]具体怎么求？—即KMP算法的实现 令k = next[ j ]（k 与j 显然具有函数关系），则 取T首与Tj处最大的相同子串 新起点 k怎么求？

(1)next[j]有何物理意义？ T=‘a b aa b c/a next[j]=maxk≤j且T.Tk.T-k-)T 模式串从第1位往右 模式串从的前一位往 直到K-1位 左经过K-1位 next[j]函数表征着模式T中最大相同前綴子串和后缀子串 真子串)的长度。 可见，模式中相似部分越多，则next[j们函数越大，它既 表示模式T字符之间的相关度越高，也表示位置以前与主串部 分匹配的字符数越多。 即：next[j]越大，模式串向右滑动得越远，与主串进行 比较的次数越少，时间复杂度就越低（时间效率）。 再想一想：如男主串是外存中一个 犬义件，治泸料法效桌安如时算法的实现

9 （1） next[ j ]有何物理意义？ next[j]函数表征着模式T中最大相同前缀子串和后缀子串 （真子串）的长度。 可见，模式中相似部分越多，则next[j]函数越大，它既 表示模式T字符之间的相关度越高，也表示j位置以前与主串部 分匹配的字符数越多。 即：next[j]越大，模式串向右滑动得越远，与主串进行 比较的次数越少，时间复杂度就越低（时间效率）。 next[ j ]＝max { k |1<k<j 且‘T1.Tk-1 ’=‘Tj-(k-1) .Tj- 1 ’} 模式串从第1位往右 直到K-1位 模式串从j的前一位往 左经过K-1位 想一想：如果主串和模式均为二 进制码流，用KMP算法效果如何？ T=‘a b a a b c a c’ 再想一想：如果主串是外存中一个 （2） next[ j ] 大文件，用具体怎么求？ KMP算法效果又如何？ —即KMP算法的实现

(2)next[jJ怎么计算？ 计算Next[j]的方法： =1时，Next[j1=0: /NeXt[j]=O表示根本不进行存符比较 当>1时，Next[j]的值为：模式串的位置从1到j-1 构成的串中所出现的首尾相同的子串的最大长度加1。 无首尾相同的子串时Next[j]的值为1。 /Next[j]=1表示从模式串头部开始进行字符比较 怎样计算模式T所有可能的失配点j所对应的next[们？ 10

10 计算Next[j]的方法： •当j=1时，Next[j]=0； //Next[j]=0表示根本不进行字符比较 •当j>1时，Next[j]的值为：模式串的位置从1到j-1 构成的串中所出现的首尾相同的子串的最大长度加1。 无首尾相同的子串时Next[j]的值为1。 // Next[j]=1表示从模式串头部开始进行字符比较 （2） next[ j ]怎么计算？ 怎样计算模式T所有可能的失配点 j 所对应的 next[j]？