題目: 有一個(gè)主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 請(qǐng)找到模式串在主串中第一次出現(xiàn)的位置
提示: 不需要考慮字符串大小寫問(wèn)題, 字符均為小寫字母
使用算法：BF算法、RK算法

BF算法

是什么

一般叫做暴力算法，也叫做樸素算法。主要思想就是把目標(biāo)串 S 的第一個(gè)字符與模式串 T 的第一個(gè)字符進(jìn)行匹配，若相等，則繼續(xù)比較S的第二個(gè)字符和 T的第二個(gè)字符；若不相等，則比較S的第二個(gè)字符和T的第一個(gè)字符，依次比較下去，直到得出最后的匹配結(jié)果。

BF算法示意圖

思路

時(shí)間復(fù)雜度：O(n*m)

• 分別初始化i,j。i和j分別從主串S 和模式串 T 第一個(gè)字母開始
• 如果相等，則繼續(xù)下一個(gè)字符
• 如果不想等，主串回退到匹配j的下一個(gè)位置
• 遍歷結(jié)束查看是否匹配的到

代碼

#define MAXSIZE 40    /* 存儲(chǔ)空間初始分配量 */
typedef char String[MAXSIZE+1]; /*  0號(hào)單元存放串的長(zhǎng)度 */

int findIndexBF(String target,String content,int startPosition) {
    int i = startPosition; // 從指定位置開始
    int j = 1;
    
    // 如果i 小于target長(zhǎng)度，且j 小于content長(zhǎng)度，循環(huán)繼續(xù)
    while (i < target[0] && j < content[0]) {
        if (target[i] == content[j]) {
            // 內(nèi)容相同，繼續(xù)
            i ++;
            j ++;
        } else {
            // 沒(méi)有匹配到，那么主串索引回退到已經(jīng)匹配過(guò)的首位
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > content[0]) {
        return i - content[0];
    }
    return -1;
}

int main(int argc, const char *argv[]) {
    printf("Hello, World!");
    return 0;
}

RK算法

是什么

通過(guò)哈希算法對(duì)主串中的 n-m+1 個(gè)子串分別求哈希值，然后逐個(gè)與模式串的哈希值比較大小。
如果某個(gè)子串的哈希值與模式串相等，那就說(shuō)明對(duì)應(yīng)的子串和模式串匹配了（這里先不考慮哈希沖突的問(wèn)題）。
因?yàn)楣Ｖ凳且粋€(gè)數(shù)字，數(shù)字之間比較是否相等是非常快速的，所以模式串和子串比較的效率就提高了。
示意圖如下：

RK算法示意圖

對(duì)比BF算法

RK算法的全稱叫Rabin-Karp 算法，是由它的兩位發(fā)明者 Rabin 和 Karp 的名字來(lái)命名的。其實(shí)是BF算法的升級(jí)版本，在BF算法中，需要每次都進(jìn)行字符串的匹配，每次需要檢查模式傳是否與主串相等，所以時(shí)間復(fù)雜度是O(n*m)。
而RK算法是通過(guò)對(duì)比字符串的哈希值（散列），哈希是數(shù)字，對(duì)比哈希的效率相對(duì)于比較字符串來(lái)說(shuō)，肯定是高了不少的，但是從時(shí)間效率上來(lái)說(shuō)，到這一步并沒(méi)有比BF少了多少。

而哈希算法的巧妙之處就在于此了，在計(jì)算字符串的哈希值時(shí)，由于a-z是26個(gè)字母，因此可以類比于十進(jìn)制，用作26進(jìn)制來(lái)計(jì)算，下面來(lái)舉個(gè)??

進(jìn)制

在對(duì)比模式串的時(shí)候可以發(fā)現(xiàn)相鄰子串的一些規(guī)律，相鄰的2個(gè)子串 s[i] 與 s[i+1] (i表示子串從主串中的起始位置,子串的長(zhǎng)度 都為m)，對(duì)應(yīng)的哈希值計(jì)算公式有交集，也就說(shuō)我們可以使用 s[i-1] 計(jì)算出 s[i] 的哈希值。
s[i+1] 實(shí)現(xiàn)上是上一個(gè)s[i]去掉最高位數(shù)據(jù),其余的m-1為字符乘以 d進(jìn)制. 再加上最后一個(gè)為字符得到,推導(dǎo)如下

相鄰子串?dāng)?shù)值比較

整個(gè) RK 算法包含兩部分，計(jì)算子串哈希值和模式串哈希值與子串哈希值之間的比較。第一部分，我們前面也分析了，可以通過(guò)設(shè)計(jì)特殊的哈希算法，只需要掃描一遍主串就能計(jì)算出所有子串的哈希值了，所以這部分的時(shí)間復(fù)雜度是 O(n)。

思路

1. 求出對(duì)應(yīng)模式串的哈希值，主串分解子串哈希值
2. 求得子串與主串中0~m字符串的哈希值(計(jì)算子串與主串0-m的哈希值)
3. 獲取d^{m-1值(因?yàn)榻?jīng)常要用d}m-1進(jìn)制值)
4. 遍歷[0,n-m], 判斷模式串HashValue A是否和其他子串的HashValue 一致.
   不一致則繼續(xù)求得下一個(gè)HashValue
   如果一致則進(jìn)行二次確認(rèn)判斷,2個(gè)字符串是否真正相等,防止哈希值沖突導(dǎo)致錯(cuò)誤

注意細(xì)節(jié):

1. 在進(jìn)入循環(huán)時(shí),就已經(jīng)得到子串的哈希值以及主串的[0,m)的哈希>值,可以直接進(jìn)行第一輪比較
2. 哈希值相等后,再次用字符串進(jìn)行比較.防止哈希值沖突
3. 如果不相等,利用在循環(huán)之前已經(jīng)計(jì)算好的st[0] 來(lái)計(jì)算后面的st[1]
4. 在對(duì)比過(guò)程,并不是一次性把所有的主串子串都求解好Hash值. 而是是借助s[i]來(lái)求解s[i+1] . 簡(jiǎn)單說(shuō)就是一邊比較哈希值,一邊計(jì)算哈希值

代碼

// 防止hash值相等，字符串不相等的情況
bool isMatch(char *mainString, int index, char *matchString, int matchLength) {
    for (int i = 0; i < matchLength; i ++) {
        if (mainString[index + i] != matchString[i]) {
            return false;
        }
    }
    return true;
}

int RK(char *mainString,char *matchString) {
    int d = 26;
    int m  = (int)strlen(mainString); // 主串長(zhǎng)度
    int n  = (int)strlen(matchString); // 模式串長(zhǎng)度
    
    unsigned int mainHash  = 0; // 子串hash
    unsigned int matchHash   = 0; // 模式串hash
    
    //d^m-1值(因?yàn)榻?jīng)常要用d^n-1進(jìn)制值)
    int hValue = 1;
    
    //求得子串與主串中0~n字符串的哈希值[計(jì)算子串與主串0-n的哈希值]
    //循環(huán)[0,n)獲取模式串A的HashValue以及主串第一個(gè)[0,n)的HashValue
    for(int i = 0; i < n; i++){
        matchHash = (d * matchHash + (matchString[i] - 'a'));
        mainHash = (d * mainHash + (mainString[i] - 'a'));
        hValue = i > 0 ? hValue * d : hValue; // 計(jì)算d^n-1進(jìn)制值
    }
    
    for (int i = 0; i <= m - n; i++) {
        if (matchHash == mainHash && isMatch(mainString, i, matchString, n)) {
            return i;
        }
        mainHash = (mainHash - hValue * (mainString[i] - 'a')) * d + (mainString[i+n] - 'a');
    }
    return -1;
}