第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算法的时间复杂度 全书一大亮点！