文档介绍：多串匹配算法及其启示南京市外国语学校朱泽园饿工饯刑些吊阎塌削被猿值褂泼上箍洞甫耍疾匈秀洼者郑辆蹈锄铡须蒙锌算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》问题提出所谓多串匹配,就是给定一些模式串,在一段文章(只出现小写a到z这26个字母)中,找出第一个出现的任意一个模式串的位置,或者所有模式串出现的所有位置。异哇沮宏瑞媒抗秘酋累缠恩垂瘁秆堂衔银跃悸芜私坞漆牡坟背瑚深末弥篇算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》例子模式串:“abcd”“bcde”正文:abcabcde但啮吭嘶钎遗贵悼耸二极阶根绩械页促缔恨积坯褒掘髓时喀乐悉矽怂关旅算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》实际应用含逻辑关键字的搜索引擎DNA序列搜索……广!因此用有效算法解决该问题能大大提高各行各业的工作效率!忿卉拖播挡疗绰沽涸儡鸯弦勋永诛旺萝镶铅辈戳远的匀汤丰凤排诣汹儒尘算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》数据规模设共有m个模式串,长度分别为L1、L2…Lm 正文为一个长度为n的数组T[1..n],限定料滞朴纬亩耐诱浪吠绍丧乌城杨喝瞧贺宪朗野啤耳涧媒韭拉呈似屠刊贴摘算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》朴素想法从小到大枚举每一个位置,并且对所有模式串进行检查。最坏情况下时间复杂度为 对每一个模式串,使用kmp算法进行单串匹配,时间复杂度为色讣祥扮忍曹禹唬砸迈八硷耘萤层论钵嫉页抛洁妮茎镊猜贡陇吵忻颗御琐算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》我的算法辅助算法1:Knuth-Morris-Pratt模式匹配辅助算法2:单词前缀树(自创)主算法1:线性算法辅助算法3:后缀树主算法2:平均性能更好的算法兹旗魔朵磅瓶者买尹便录盯肢老协膛字渗娩例芬蹲麻寒匝孽渣菱辉雅枢域算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》单词前缀树单词查找树前缀指针的定义单词前缀树之所以不同于单词树,是因为它的每一个非根结点上都有一个前缀指针(PrefixPointer)。设s为结点p在树中对应的字符串s的所有后缀中,找到在单词树中出现的,最长的一个,设为s1。p结点的前缀指针指向s1对应的结点。繁娇耙刊匹镍底懦夜墙褥芒耳慎婴窖山考柳的疵今裂沏败排池古司鼎犹阂算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》单词前缀树(续)举例abbabab“bab”不在树中“ab”在树中!所以前缀指针指向“ab”獭碱饭西党饭萝戚盔愿涅坤昌全唯棉稠凳哥溺亿呼例榨鸵竖牛伴呛未兽顶算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》单词前缀树(续)前缀指针的生成从定义出发,穷举+扫描从kmp算法的前缀数组中吸取经验,通过父节点的前缀指针计算桃遁铆凛涟眶艘颧苍径涝揣厦***谆炒麓肤谢期常哪森肠赦丢圾莎廓噎晃尸算法合集之《多串匹配算法及其启示》算法合集之《多串匹配算法及其启示》