最详细最容易理解的BM算法简介.ppt
《最详细最容易理解的BM算法简介.ppt》由会员分享,可在线阅读,更多相关《最详细最容易理解的BM算法简介.ppt(35页珍藏版)》请在三一文库上搜索。
1、Boyer-Moore算法简介,与之前算法的比较,暴力算法 与 KMP算法 都是基于前缀比较的算法 BM算法则是基于后缀比较,而且BM算法其实上包含两个并行的算法: 坏字符算法 好后缀算法 相同点:这些算法都是对文本串从左往右分析的,朴素的思想-坏字符算法,S =“FINDINAHAYSTACKNEEDLEINA” T =“NEEDLE” FINDINAHAYSTACKNEEDLEINA NEEDLE,朴素的思想-坏字符算法,S =“FINDINAHAYSTACKNEEDLEINA” T =“NEEDLE” FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE,朴素的思
2、想-坏字符算法,S =“FINDINAHAYSTACKNEEDLEINA” T =“NEEDLE” FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE NEEDLE,朴素的思想-坏字符算法,S =“FINDINAHAYSTACKNEEDLEINA” T =“NEEDLE” FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE NEEDLE NEEDLE,朴素的思想-好后缀算法,CASE 1 S= *BABCDE* T= ABCDEFGBCDE,朴素的思想-好后缀算法,CASE 1 S= *BABCDE* T= ABCDEFGBCDE T= AB
3、CDEFGBCDE,朴素的思想-好后缀算法,CASE 2 S= *BABCDE* T= CDECDEGBCDE,朴素的思想-好后缀算法,CASE 2 S= *BABCDE* T= CDECDEGBCDE T= CDECDEGBCDE,坏字符算法,FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE NEEDLE NEEDLE 上面的N,S,N是坏字符,显然在该算法中存在两种情况: 1.坏字符不在模式串中 2.坏字符在模式串中,Case 1,坏字符不在模式串中 *TLE* NEEDLE NEEDLE Shift = strlen(模式串)-position(坏) Shif
4、t = 6 - 2,Case 2a,坏字符在模式串中 *NLE* NEEDLE NEEDLE Shift =最右的坏字符位置position(坏) Shift = 5 - 2,Case 2b,坏字符在模式串中 *ELE* NEEDLE,Case 2b,坏字符在模式串中 *ELE* NEEDLE NEEDLE 会有倒退 NEEDLE 不能预处理 上面两种设计思想都可行,各有优缺点,预处理-坏字符,Shift = bmBcSi-(m-1-i) void preBmBc(char *S, int m, int bmBc) int i; for (i = 0; i ASIZE; +i) /ASIZE=
5、256 bmBci = m; for (i = 0; i =m - 1; +i) bmBcSi = m - i - 1; ,m-i,-1,预处理-坏字符,void preBmBc(char *S, int m, int bmBc) int i; for (i = 0; i ASIZE; +i) /ASIZE=256 bmBci = m; for (i = 0; i =m - 1; +i) bmBcSi = m - i - 1; 这是会有倒退的算法设计,优点在于能够对模式串预处理,预处理-坏字符,void preBmBc(char *S, int m, int bmBc) int i; for
6、(i = 0; i ASIZE; +i) /ASIZE=256 bmBci = m; for (i = 0; i =m - 1; +i) bmBcSi = m - i - 1; 这是会有倒退的算法设计,优点在于能够对模式串预处理,O(M),思考题,为什么坏字符算法虽然倒退但是我们还是用这个算法呢? 解答: 坏字符算法虽然倒退,但是BM算法中好后缀算法是确保不后退的,我们每次移动是取两个算法的最大值。这样一结合就保证了模式串不会倒退。 而坏字符算法虽然后退但是有着能够预处理,代码实现简单,时间复杂度低的特点,所以被广为接受。在后面的SUNDAY 算法等改进算法中有的是使用了不后退的思路。,好后缀
7、算法,当好后缀在模式串中重复出现时 S= *BABCDE* T= ABCDEFGBCDE,好后缀算法,当好后缀在模式串中重复出现时 S= *BABCDE* T= ABCDEFGBCDE T= ABCDEFGBCDE,好后缀算法,模式串中没有子串匹配好后缀 S= *BABCDE* T= CDECDEGBCDE,好后缀算法,模式串中没有子串匹配好后缀 S= *BABCDE* T= CDECDEGBCDE T= CDECDEGBCDE 此时需要寻找模式串的一个最长前缀CDE,并让该前缀等于好后缀BCDE的后缀,寻找到该前缀后,让该前缀和好后缀对齐即可。,好后缀算法,模式串中没有子串匹配上好后缀,并且
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 详细 容易 理解 BM 算法 简介
链接地址:https://www.31doc.com/p-8920500.html