算法合集之《多串匹配算法及其启示》.ppt

文档介绍：多串匹配算法及其启示
南京市外国语学校
朱泽园
问题提出
所谓多串匹配,就是给定一些模式串,在一段文章(只出现小写a到z这26个字母)中,找出第一个出现的任意一个模式串的位置,或者所有模式串出现的所有位置。
例子
模式串:“abcd”“bcde”
正文:
abcabcde
实际应用
含逻辑关键字的搜索引擎
DNA序列搜索
……
广!
因此用有效算法解决该问题能大大提高各行各业的工作效率!
数据规模
设共有m个模式串,长度分别为L1、L2…Lm正文为一个长度为n的数组T[1..n],限定
朴素想法
从小到大枚举每一个位置,并且对所有模式串进行检查。最坏情况下时间复杂度为
对每一个模式串,使用kmp算法进行单串匹配,时间复杂度为
我的算法
辅助算法1:Knuth-Morris-Pratt模式匹配
辅助算法2:单词前缀树(自创)
主算法1:线性算法
辅助算法3:后缀树
主算法2:平均性能更好的算法
单词前缀树
单词查找树
前缀指针的定义
单词前缀树之所以不同于单词树,是因为它的每一个非根结点上都有一个前缀指针(Prefix Pointer)。
设s为结点p在树中对应的字符串
s的所有后缀中,找到在单词树中出现的,最长的一个,设为s1。
p结点的前缀指针指向s1对应的结点。
单词前缀树(续)
举例
a
b
b
a
b
a
b
“bab”不在树中
“ab”在树中!
所以前缀指针指向“ab”
单词前缀树(续)
前缀指针的生成
从定义出发,穷举+扫描
从kmp算法的前缀数组中吸取经验,通过父节点的前缀指针计算