5算法设计技术5-算法优化技术_398104690

《5算法设计技术5-算法优化技术_398104690》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2010-2011春季学期数据结构课程讲义算法设计技术吴及wuji_ee@tsinghua.edu.cn清华大学电子工程系2011年12月内容提要算法设计技术算法优化技术计算复杂性理论简介数据与算法吴及2(20230253)电子工程系内容提要算法优化技术输入增强技术预构造技术时空平衡算法的组合数据与算法吴及3(20230253)电子工程系内容提要算法优化技术输入增强技术预构造技术时空平衡算法的组合数据与算法吴及4(20230253)电子工程系输入增强字符串匹配的KMP算法

2、字符串匹配的Horspool算法计数排序数据与算法吴及5(20230253)电子工程系KMP算法Knüth-Morris-Pratt算法(1977)KMP算法按自左向右的方向匹配在匹配过程中，当模式P丌匹配时，应尽量向右移动最大距离，以避免重复比较i??????j????????????数据与算法吴及6(20230253)电子工程系KMP算法KMP算法移动模式串的步骤一:设?是模式?的丌匹配位置，在?0,⋯,?−1中找出?0,⋯,?−1的前缀中最长的一个，它恰好等于?1,⋯,?−1的后缀

3、中最长的一个?????????0,⋯,?−1=?????，其前缀为：?，??，???，????，??????1,⋯,?−1=????，其后缀为：????，???，??，?因此模式?在?−1位置最长的匹配串为??，称为部分匹配串数据与算法吴及7(20230253)电子工程系KMP算法KMP算法的预处理函数Next对模式串进行预处理，逐个位置求取部分匹配串，并用????纪彔其长度?012345?????????????−1001123当丌匹配的字符位于??≠??时，模式串：??????−1，

4、当?>0主串：?丌变，或+1数据与算法吴及8(20230253)电子工程系KMP算法KMP算法移动模式串的步骤二:然后向右移动模式串，使这个最长的前缀对准相应的后缀所处?的位置?????c?abaaba前缀后缀abaaba移动步数只不模式串?有关，而不目标串?无关数据与算法吴及9(20230253)电子工程系KMP算法丼例?=????4=1?=????0=0?=????3=0?++数据与算法吴及10(20230253)电子工程系Horspool算法基于启发式规则的Horspool算法：

5、Looking-glass:将模式?不?的子序列进行反向比较character-jump:当丌匹配的位置位于??=c≠??如果?包含?，那么移动?使?在?中的最后一次出现??对准??否则，移动?使?0对准??+1数据与算法吴及11(20230253)电子工程系Horspool算法预处理函数Last-Occurence根据模式串?预先计算字母表的Last-Occurence函数?:?→?对于每个?∈?，?按以下规则计算1.如果?在?中出现，那么?把?映射到它在?中出现的最后位置2.否则，即?丌

6、在?中出现，那么?把?映射到-1????:??=??∈???=−1?∉?数据与算法吴及12(20230253)电子工程系Horspool算法例如字符表Σ=?,?,?,?,子串?="??????"??????0123Σ??????453-1函数?的计算结果用一个数组???????保存，其中?????:Σ→0∪?+数据与算法吴及13(20230253)电子工程系Horspool算法预处理函数的实现#defineNUM128intL[NUM];voidlast_occurence(char*P){i

7、ntm＝strlen(P);//取模式P的长度inti;for(i=0;i

8、)电子工程系Horspool算法情形二：?≤?+1，模式串?移动距离：?=1模式串最后一个字符对应主串位置为:?+1+?−1−?=?+?−?这也是下一次比较的主串位置数据与算法吴及16(20230253)电子工程系Horspool算法intboyer_moore_match(charT[],charP[]){intn=strlen(T);intm=strlen(P);//求目标串和模式串的长度last_occurenc