串(Sequence)
◼ 本课程研究的串是开发中非常熟悉的字符串，是由若干个字符组成的有限序列
◼字符串 thank 的前缀(prefix)、真前缀(proper prefix)、后缀(suffix)、真后缀(proper suffix)
串匹配算法
◼ 本课程主要研究串的匹配问题，比如
查找一个模式串(pattern)在文本串(text)中的位置
◼ 几个经典的串匹配算法
蛮力(Brute Force)
KMP
Boyer-Moore
Karp-Rabin
Sunday
◼本课程用 tlen 代表文本串 text 的长度，plen 代表模式串 pattern 的长度
蛮力(Brute Force)
◼ 以字符为单位，从左到右移动模式串，直到匹配成功
◼蛮力算法有 2 种常见实现思路
蛮力1 – 执行过程
蛮力1 – 实现
蛮力1 – 优化
◼ 此前实现的蛮力算法，在恰当的时候可以提前退出，减少比较次数 pi=2
◼因此，ti 的退出条件可以从 ti < tlen 改为
ti – pi <= tlen – plen
ti – pi 是指每一轮比较中 text 首个比较字符的位置
蛮力1 – 优化实现
蛮力2 – 执行过程
蛮力2 – 实现
蛮力 – 性能分析
◼n 是文本串长度，m 是模式串长度
◼ 最好情况
只需一轮比较就完全匹配成功，比较 m 次( m 是模式串的长度)
时间复杂度为 O(m)
◼ 最坏情况(字符集越大，出现概率越低)
执行了 n – m + 1 轮比较( n 是文本串的长度)
每轮都比较至模式串的末字符后失败(m – 1 次成功，1 次失败)
时间复杂度为 O(m ∗ (n − m + 1))，由于一般 m 远小于 n，所以为 O(mn)
KMP
◼KMP 是 Knuth–Morris–Pratt 的简称(取名自3位发明人的名字)，于1977年发布
蛮力 vs KMP
◼ 对比蛮力算法，KMP的精妙之处:充分利用了此前比较过的内容，可以很聪明地跳过一些不必要的比较位置
KMP – next表的使用
◼KMP 会预先根据模式串的内容生成一张 next 表(一般是个数组)
KMP – 核心原理
◼当 d、e 失配时，如果希望 pattern 能够一次性向右移动一大段距离，然后直接比较 d、c 字符
前提条件是 A 必须等于 B
◼所以 KMP 必须在失配字符 e 左边的子串中找出符合条件的 A、B，从而得知向右移动的距离
◼向右移动的距离:e左边子串的长度 – A的长度，等价于:e的索引 – c的索引
◼且 c的索引 == next[e的索引]，所以向右移动的距离:e的索引 – next[e的索引]
◼总结
如果在 pi 位置失配，向右移动的距离是 pi – next[pi]，所以 next[pi] 越小，移动距离越大
next[pi] 是 pi 左边子串的真前缀后缀的最大公共子串长度
KMP – 真前缀后缀的最大公共子串长度
KMP – 得到next表
◼将最大公共子串长度都向后移动 1 位，首字符设置为 负1，就得到了 next 表
KMP – 负1的精妙之处
◼ 相当于在负1位置有个假想的通配字符(哨兵)
匹配成功后 ti++、pi++
KMP – 主算法实现
KMP – 为什么是“最大“公共子串长度?
◼ 假设文本串是AAAAABCDEF，模式串是AAAAB
◼应该将1、2、3中的哪个值赋值给 pi 是正确的?
◼将 3 赋值给 pi
向右移动了 1 个字符单位，最后成功匹配
◼将 1 赋值给 pi
向右移动了 3 个字符单位，错过了成功匹配的机会
◼ 公共子串长度越小，向右移动的距离越大，越不安全
◼ 公共子串长度越大，向右移动的距离越小，越安全
KMP – next表的构造思路
◼已知 next[i] == n
1 如果 pattern.charAt(i) == pattern.charAt(n)
那么 next[i + 1] == n + 1
2 如果 pattern.charAt(i) != pattern.charAt(n)
已知 next[n] == k
如果 pattern.charAt(i) == pattern.charAt(k)
✓那么 next[i + 1] == k + 1
如果 pattern.charAt(i) != pattern.charAt(k)
✓将 k 代入 n ，重复执行 2
KMP – next表的代码实现
KMP – next表的不足之处
◼假设文本串是 AAABAAAAB ，模式串是 AAAAB
◼ 在这种情况下，KMP显得比较笨拙
KMP – next表的优化思路
◼已知:next[i] == n，next[n] == k
◼如果 pattern[i] != d，就让模式串滑动到 nexti位置跟 d 进行比较
◼如果 pattern[n] != d，就让模式串滑动到 nextn位置跟 d 进行比较
◼如果 pattern[i] == pattern[n]，那么当 i 位置失配时，模式串最终必然会滑到 k 位置跟 d 进行比较
所以 next[i] 直接存储 nextn即可
KMP – next表的优化实现
KMP – next表的优化效果
KMP – 性能分析
◼KMP 主逻辑
最好时间复杂度:O(m)
最坏时间复杂度:O(n)，不超过O(2n)
◼next 表的构造过程跟 KMP 主体逻辑类似
时间复杂度:O(m)
◼KMP 整体
最好时间复杂度:O(m)
最坏时间复杂度:O(n + m)
空间复杂度: O(m)
蛮力 vs KMP
◼ 蛮力算法为何低效?
◼ 当字符失配时
蛮力算法
✓ti 回溯到左边位置
✓pi 回溯到 0
KMP 算法
✓ti 不必回溯
✓pi 不一定要回溯到 0
