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

BF算法

BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是將目標(biāo)串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)次比較，時間復(fù)雜度為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 算法，是為了紀(jì)念它的兩個發(fā)明者而這樣命名的。 這個算法其實就是剛剛 BF 算法的升級版。

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

解題思路

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

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

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

3. 主串拆分的子串之間的關(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')

4. 處理哈希沖突

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

代碼實現(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;
}