网站建设包括备案吗,wordpress 主循环调用,出口网站建设方案,郑州医科大附属男科医院1. WM#xff08;Wu-Manber#xff09;算法的简单理解#xff1a;#xff08;1#xff09;WM算法需要的参数#xff1a;∑#xff1a;字母集c#xff1a; 字母集数目m#xff1a;模式串集合中#xff0c;字符串长度最小的模式串的长度B#xff1a;字符块长度#…1. WMWu-Manber算法的简单理解 1WM算法需要的参数 ∑字母集 c 字母集数目 m模式串集合中字符串长度最小的模式串的长度 B字符块长度是shift表的索引一般取2或者3 h当前扫描过程中长度为B的模式串子串 T文本串 N文本串总长度 PP1, P2....Pk模式串集合 k模式串的数目 C前缀长度PREFIX表使用 2WM算法的时间复杂度 OBN/kM由此可以看出WM使用于大规模的模式串集合且模式串集合中最小长度较大的场景 3WM算法的核心思想 WM算法是对BM算法的延伸继承用BM算法的核心框架用字符块来计算shift表取代坏字符表进行跳转在进行匹配时用hash和prefix计算前后缀的hash值来从众多可选的模式串中快速筛选出正确匹配的模式串。 4WM算法的三张核心表 shift表用于记录文本串向右移动的长度即一张跳转表ps有点类似BM算法的坏字符表不过BM是针对单字符WM是针对字符块。 hash表hash表记录了所有模式串后缀长度为B与模式串本身的映射关系。当shift[h]0时B与对应模式串P的映射关系但是存在一对多的映射因为模式串集合中存在相同后缀的模式串所以hash表的value应该是一个链表的形式存储多个模式串ps当shift[h]0时说明匹配到了某模式串此时要用hash表查匹配到了哪个模式串P prefix表prefix记录了所有模式串前缀长度为B与模式串本身的映射关系。同hash表一样B与对应模式串P的映射关系存在一对多所以prefix表的value也是一个链表的形式存储多个模式串。pshash与prefix两个表取交集极大地缩小了需要匹配的次数 2. WMWu-Manber算法的匹配过程 当B个字符构成的子串h在模式串集合中没有匹配即shift[h]0则跳转的距离是m-B1相对保守的策略 当B个字符构成的子串h在模式串集合中有匹配且非后缀即shift[h]0则跳转的距离是shift[h]相对安全的滑动 当B个字符构成的子串h在模式串集合中且是后缀即shift[h]0则查hash和prefix表确定匹配到了哪个模式串 3. WMWu-Manber算法的简单例子来自joylnwang专栏-WM算法详解 目标串target[1...10]dcbacabcde模式结合P{abcde,bcbde,abcabe}psm5B2k3C2预处理后得到的三张表如下所示 WM算法的匹配过程是 1从i5因为m5开始执行算法首先我们发现target[4...5] actarget[i-B1](5-21)SHIFT表中不存在ac所以i i4 shift表中没找到则 i m-B1 2此时i9发现target[8...9]cd查SHIFT[cd]1所以i SHIFT[cd]。 3此时i10然后发现target[9...10]de 查SHIFT[de]0表明可能出现匹配到模式串的情况。 4查HASH[de]有两个模式串abcde和bcbde在target中取长度为C的从i-m1开始的子串即target[6...7] ab查PREFIX[ab] abcde。此时确定模式串是abcde。 4. WMWu-Manber算法的程序实例 转载于:https://www.cnblogs.com/ladawn/p/9281509.html
