美文网首页
2020-10-15

2020-10-15

作者: Leon_b741 | 来源:发表于2020-10-15 11:44 被阅读0次

    BM算法笔记:

    3,滑动距离函数:  

    为方便讨论,BM算法的关键是,对给定的模式T="t0t1…tm"定义一个从字符到正整数的映射:  

    dist :c->{1,2,…,m+1}  

    函数dist称为滑动距离函数,它给出了正文中可能出现的任意字符在模式中的位置。函数dist定义如下:  

    dist(c) = m-j  j为c在模式中的下标,以后面的为准  

    dist(c) = m+1  若c不在模式中或c = tm  

    例如,T="pattern",则dist(p)= 6 – 0 = 6, dist(a)= 6 – 1 =5,  dist(t)= 6 – 3 =3 ,dist(e)= 2, dist(r)= 1, dist(n)= 6 + 1 = 7。  

    4,BM算法的基本思想是:假设将主串中自位置i起往左的一个子串与模式进行从右到左的匹配过程中,若发现不匹配,则下次应从主串的i + dist(si)位置开始重新进行新一轮的匹配,其效果相当于把模式和主串向右滑过一段距离dist(si),即跳过dist(si)个字符而无需进行比较。  

    如这样一个例子:

    从FINDINAHAYSTACKNEEDLEINA中查找NEEDLE的过程:

    i    j    00    01    02    03    04    05    06    07    08    09    10    11    12     13    14    15    16    17    18    19    20    21    22    23

    F      I       N      D     IA      H     A      YS      T      A       C     KN E     D      L     E I       N      A

    0   5   N     E      E      D     LE

    5   5                                           N     E      E      D     LE

    11 4                                                                                           N       E       E     DL E

    15 0N     E      E     D     L     E

    排版不是很好排,请大家见谅

    第一步:i=5,j=5失败 dist(N)= 5 所以右移到5+5=10处

    第二步:i=10,j=5失败 无dist(S) 所以右移到10+6 =16处

    第三步:i=15,j=4失败 dist(N) = 5 所以右移到15+5 = 20处匹配成功

    实例代码: 

    #include<iostream>

    #include<stdlib.h>

    #include<cstring>

    using namespace std;

    int dist(char *t,char ch) { //算出dist()的值

    int len = strlen(t);      //求子串的长度

    int i = len - 1; //用于遍历子串内各字符的下标并从0开始计数

    if (ch == t[i])

    return len;

    i--;

    while (i >= 0) {

    if (ch == t[i]) {

    return len - 1 - i; //如果

    }

    else

    {

    i--;

    }

    }

    return len;

    }

    int BM(char *s,char *t) {

    int x = strlen(s);

    int y = strlen(t);

    int i = y - 1;

    int j = y - 1;

    while (j >= 0&&i<x) {

    if (s[i] == t[j]) {

    i--;

    j--;

    }

    else {

    i += dist(t,s[i]);//移动位置为坏字符在主串的位置+该字符在子串的值

    j = y - 1; //子串回到最右边

    }

    }

    if (j < 0) {

    return i + 1;

    }

    return -1;

    }

    int main() {

    char a[] = "ababcabcacbab";

    char b[] = "abcac";

    cout << BM(a, b) << endl;

    system("pause");

    return 0;

    }

    相关文章

      网友评论

          本文标题:2020-10-15

          本文链接:https://www.haomeiwen.com/subject/lmvnpktx.html