數(shù)據(jù)結(jié)構(gòu)與算法13-BF&RK算法

有一個主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 請找到模式串在主串中第一次出現(xiàn)的位置;
提示: 不需要考慮字符串大小寫問題, 字符均為小寫字母

BF算法

BF算法弓乙，即暴力(Brute Force)算法日麸，是普通的模式匹配算法，BF算法的思想就是將目標串S的第一個字符與模式串T的第一個字符進行匹配毁靶，若相等，則繼續(xù)比較S的第二個字符和 T的第二個字符优构；若不相等疗琉，則比較S的第二個字符和T的第一個字符，依次比較下去秒咐，直到得出最后的匹配結(jié)果谬晕。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)腊敲。

代碼實現(xià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 算法击喂，是為了紀念它的兩個發(fā)明者而這樣命名的。這個算法其實就是剛剛 BF 算法的升級版碰辅。

在 BF 算法中懂昂，每次都要對 m 個字符逐個進行比較，這就大大降低了算法的效率没宾。這時候凌彬，我們引入哈希算法，對子串逐個求哈希值榕吼，然后與模式串的哈希值進行比較來判斷兩個子串是否匹配。在不考慮哈希沖突的情況下勉失，數(shù)字之間的比較就非掣迹快了。

解題思路

1.首先把字母轉(zhuǎn)換成數(shù)字乱凿，將字母-'a'的值單純字母的對應(yīng)的數(shù)字

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

將小寫字母字符串轉(zhuǎn)換成數(shù)字顽素，利用字母26進制

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

主串拆分的子串之間的關(guān)系

例如
主串： 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

子串哈希值求解的規(guī)律：

相鄰的2個子串s[i]與s[i + 1]，對應(yīng)的哈希值計算公式有交集徒蟆，也就是說我們可以使用s[i - 1] 計算出s[i]的哈希值胁出。

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

處理哈希沖突

設(shè)計更復雜的哈希公式
如果哈希值相等，重新核實

代碼實現(xiàn)

#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;
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者