最详细最容易理解的BM算法简介课件

1、最详细最容易理解的bm算法简介boyer-moore算法简介最详细最容易理解的bm算法简介与之前算法的比较 暴力算法 与 kmp算法 都是基于前缀比较的算法 bm算法则是基于后缀比较，而且bm算法其实上包含两个并行的算法： 坏字符算法 好后缀算法相同点：这些算法都是对文本串从左往右分析的最详细最容易理解的bm算法简介 朴素的思想-坏字符算法 s =“findinahaystackneedleina” t =“needle” findinahaystackneedleina needle最详细最容易理解的bm算法简介 朴素的思想-坏字符算法 s =“findinahaystackneedlein

2、a” t =“needle” findinahaystackneedleina needle needle最详细最容易理解的bm算法简介 朴素的思想-坏字符算法 s =“findinahaystackneedleina” t =“needle” findinahaystackneedleina needle needle needle最详细最容易理解的bm算法简介 朴素的思想-坏字符算法 s =“findinahaystackneedleina” t =“needle” findinahaystackneedleina needle needle needle needle最详细最容易理解的b

3、m算法简介 朴素的思想-好后缀算法 s= *babcde* t= abcdefgbcde最详细最容易理解的bm算法简介 朴素的思想-好后缀算法 s= *babcde* t= abcdefgbcde t= abcdefgbcde最详细最容易理解的bm算法简介 朴素的思想-好后缀算法 s= *babcde* t= cdecdegbcde最详细最容易理解的bm算法简介 朴素的思想-好后缀算法 s= *babcde* t= cdecdegbcde t= cdecdegbcde最详细最容易理解的bm算法简介坏字符算法 findinahaystackneedleina needle needle need

4、le needle 上面的n,s,n是坏字符，显然在该算法中存在两种情况：1.坏字符不在模式串中 2.坏字符在模式串中最详细最容易理解的bm算法简介case 1 *tle* needle needle shift = strlen(模式串)-position(坏) shift = 6 - 2最详细最容易理解的bm算法简介case 2a *nle* needle needle shift =最右的坏字符位置position(坏) shift = 5 - 2最详细最容易理解的bm算法简介case 2b *ele* needle最详细最容易理解的bm算法简介case 2b *ele* needle

5、needle 会有倒退 needle 不能预处理 上面两种设计思想都可行，各有优缺点最详细最容易理解的bm算法简介预处理-坏字符 shift = bmbcsi-（m-1-i) 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;m-i-1最详细最容易理解的bm算法简介预处理-坏字符 void prebmbc(char *s, int m, int bmbc) int i;

6、for (i = 0; i asize; +i) /asize=256 bmbci = m; for (i = 0; i =m - 1; +i) bmbcsi = m - i - 1; 这是会有倒退的算法设计，优点在于能够对模式串预处理最详细最容易理解的bm算法简介预处理-坏字符 void prebmbc(char *s, int m, int bmbc) int i; for (i = 0; i asize; +i) /asize=256 bmbci = m; for (i = 0; i =0；-i) q=i; while(q=0&pq=pm-1-(i-q) -q; suffixi=

7、i-q;最详细最容易理解的bm算法简介预处理-好后缀void prebmgs(char *x, int m, int bmgs) int i, j, suffxsize; suffixes(x, m, suff); /对模式串进行预处理 for (i = 0; i = 0; -i) if (suffi = i + 1) /如果找到一个最大前缀 for (; j m - 1 - i; +j) if (bmgsj = m) bmgsj = m - 1 - i; for (i = 0; i = m - 2; +i) bmgsm - 1 - suffi = m - 1 - i;最详细最容易理解的bm算

8、法简介预处理-好后缀void prebmgs(char *x, int m, int bmgs) int i, j, suffxsize; suffixes(x, m, suff); /对模式串进行预处理 for (i = 0; i = 0; -i) if (suffi = i + 1) /如果找到一个最大前缀 for (; j m - 1 - i; +j) if (bmgsj = m) bmgsj = m - 1 - i; for (i = 0; i = m - 2; +i) bmgsm - 1 - suffi = m - 1 - i;模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上

9、好后缀，但找不到一个最大前缀的情况不到一个最大前缀的情况最详细最容易理解的bm算法简介预处理-好后缀void prebmgs(char *x, int m, int bmgs) int i, j, suffxsize; suffixes(x, m, suff); /对模式串进行预处理 for (i = 0; i = 0; -i) if (suffi = i + 1) /如果找到一个最大前缀 for (; j m - 1 - i; +j) if (bmgsj = m) bmgsj = m - 1 - i; for (i = 0; i = m - 2; +i) bmgsm - 1 - suffi

10、= m - 1 - i;模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况不到一个最大前缀的情况模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况得到一个最大前缀的情况最详细最容易理解的bm算法简介预处理-好后缀void prebmgs(char *x, int m, int bmgs) int i, j, suffxsize; suffixes(x, m, suff); /对模式串进行预处理 for (i = 0; i = 0; -i) if (suffi = i + 1) /如果找到一个最大前缀 for (;

11、j m - 1 - i; +j) if (bmgsj = m) bmgsj = m - 1 - i; for (i = 0; i = m - 2; +i) bmgsm - 1 - suffi = m - 1 - i;模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况不到一个最大前缀的情况模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况得到一个最大前缀的情况模式串中有子串匹配上好后缀模式串中有子串匹配上好后缀最详细最容易理解的bm算法简介预处理-好后缀void prebmgs(char *x, int m, int

12、 bmgs) int i, j, suffxsize; suffixes(x, m, suff); /对模式串进行预处理 for (i = 0; i = 0; -i) if (suffi = i + 1) /如果找到一个最大前缀 for (; j m - 1 - i; +j) if (bmgsj = m) bmgsj = m - 1 - i; for (i = 0; i = m - 2; +i) bmgsm - 1 - suffi = m - 1 - i;最详细最容易理解的bm算法简介算法主体int bm_search(char* s ,char* t)j = 0；while (j = 0 & ti =si + j; -i) if (i 0) match； else j += max(bmgsi, bmbcti-（m-1-i)；最详细最容易理解的bm算法简介算法主体i