美文网首页
数据结构与算法-BF&RK算法

数据结构与算法-BF&RK算法

作者: SK_Wang | 来源:发表于2020-04-22 15:30 被阅读0次

    有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 请找到模式串在主串中第一次出现的位置;
    提示: 不需要考虑字符串大小写问题, 字符均为小写字母

    BF算法

    BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。

    算法思想

    首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M]为止;若S[1]和T[1]不等,则S向右移动一个字符的位置,再依次进行比较。如果存在k,1≤k≤N,且S[k+1…k+M]=T[1…M],则匹配成功;否则失败。
    该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M * N)。

    代码实现

    int Index(String S, String T, int pos) {
        int i = pos;
        int j = 1;
        while (i <= S[0] && j <= T[0]) {
            if (S[i] == T[j]) {
                i++;
                j++;
            } else {
                i = i - j + 2;
                j = 1;
            }
        }
        
        if (j > T[0]) {
            return i - T[0];
        } else {
            return -1;
        }
        
        return 0;
    }
    

    RK算法

    RK 算法的全称叫作 Rabin-Karp 算法,是为了纪念它的两个发明者而这样命名的。 这个算法其实就是刚刚 BF 算法的升级版。

    在 BF 算法中,每次都要对 m 个字符逐个进行比较,这就大大降低了算法的效率。这时候,我们引入哈希算法,对子串逐个求哈希值,然后与模式串的哈希值进行比较来判断两个子串是否匹配。在不考虑哈希冲突的情况下,数字之间的比较就非常快了。

    解题思路

    1.首先把字母转换成数字,将字母-'a'的值单纯字母的对应的数字

    例如
    a - a = 0;
    b - a = 1;
    c - a = 2;

    1. 将小写字母字符串转换成数字,利用字母26进制

    例如
    “cba” = 'c' * 26 ^ 2 + 'b' * 26 ^ 1 + 'a' * 26 ^ 0
    “cba” = 2 * 26 ^ 2 + 1 * 26 ^ 1 + 0 * 26 ^ 0

    1. 主串拆分的子串之间的关系

    例如
    主串: d b c e d b
    = 3 * 26 ^ 2 + 1 * 26 ^ 1 + 2 * 26 ^ 0
    主串: d b c e d b
    = 1 * 26 ^ 2 + 2 * 26 ^ 1 + 4 * 26 ^ 0

    子串哈希值求解的规律:

    相邻的2个子串s[i]与s[i + 1],对应的哈希值计算公式有交集,也就是说我们可以使用s[i - 1] 计算出s[i]的哈希值。

    St[i] = (St[i - 1] - d ^ (m - 1) * (s[i] - 'a')) * d + (s[i + m] - 'a')

    1. 处理哈希冲突
    • 设计更复杂的哈希公式
    • 如果哈希值相等,重新核实

    代码实现

    #define d 26
    
    int isMatch(char *S, int i, char *P, int m) {
        int is, ip;
        for (is = i, ip = 0; is != m && ip != m; is++, ip++) {
            if (S[is] != P[ip]) {
                return 0;
            }
        }
        
        return 1;
    }
    
    /*
     d ^ (m - 1) 位的值
     */
    int getMaxValue(int m) {
        int j = 1;
        for (int i = 0; i < m - 1; i++) {
            j = j * d;
        }
        return j;
    }
    
    int Index(char *S, char *P) {
        int n = (int)strlen(S);
        int m = (int)strlen(P);
        
        unsigned int A = 0;
        unsigned int St = 0;
        
        for (int i = 0; i != m; i++) {
            A = (d * A + (P[i] - 'a'));
            St = (d * St + (S[i] - 'a'));
        }
        
        int hValue = getMaxValue(m);
        for (int i = 0; i <= n - m; i++) {
            if (A == St && isMatch(S, i, P, m)) {
                return i + 1;
            }
            St = (St - hValue * (S[i] - 'a')) * d + (S[i + m] - 'a');
        }
        
        return -1;
    }
    

    Demo:https://github.com/ShoukaiWang/DataStructuresAndAlgorithms

    相关文章

      网友评论

          本文标题:数据结构与算法-BF&RK算法

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