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

RK算法
核心：將主串中的子串換算成哈希值，與模式串的哈希值進(jìn)行比對(duì)
缺點(diǎn)：存在哈希沖突，在最后作校驗(yàn)解決
RK算法核心思想

子串哈希值求解規(guī)律:
相鄰的2個(gè)子串 s[i] 與 s[i+1] (i表示子串從主串中的起始位置,子串的長(zhǎng)度都為m). 對(duì)應(yīng)的哈希值計(jì)算公式有交集. 也就說(shuō)我們可以使用s[i-1]計(jì)算出s[i]的哈希值;

圖1. 相鄰的兩個(gè)子串

圖2. 兩個(gè)子串的換算關(guān)系

圖3. 哈希值的換算公式

圖1中
a. s[i] = s[2] = 1 x 10^2 + 2 x 10^1 + 7 x 10^0
b. s[i+1] = s[3] = 2 x 10^2 + 7 x 10^1 + 4 x10^0
由a，b可得
s[3] = (s[2] - 10^2 x s[2]) x 10 + s[2+3]

代碼實(shí)現(xiàn)

//d 表示進(jìn)制
#define d 26

//4.解決哈希沖突. 當(dāng)前發(fā)現(xiàn)模式串和子串的HashValue 是一樣的時(shí)候.還是需要二次確認(rèn)2個(gè)字符串是否相等.
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;
}

//3.算出最d進(jìn)制下的最高位
//d^(m-1)位的值;
int getMaxValue(int m){
    int h = 1;
    for(int i = 0;i < m - 1;i++){
        h = (h*d);
    }
    
    return h;
}

/*
 * 字符串匹配的RK算法
 * Author：Rabin & Karp
 * 若成功匹配返回主串中的偏移，否則返回-1
 */
int RK(char *S, char *P)
{
    //1. n:主串長(zhǎng)度, m:子串長(zhǎng)度
    int m  = (int) strlen(P);
    int n  = (int) strlen(S);
    printf("主串長(zhǎng)度為:%d,子串長(zhǎng)度為:%d\n",n,m);
    
    //A.模式串的哈希值; St.主串分解子串的哈希值;
    unsigned int A   = 0;
    unsigned int St  = 0;
    
    //2.求得子串與主串中0~m字符串的哈希值[計(jì)算子串與主串0-m的哈希值]
    //循環(huán)[0,m)獲取模式串A的HashValue以及主串第一個(gè)[0,m)的HashValue
    //此時(shí)主串:"abcaadddabceeffccdd" 它的[0,2)是ab
    //此時(shí)模式串:"cc"
    //cc = 2 * 26^1 + 2 *26 ^0 = 52+2 = 54;
    //ab = 0 * 26^1 + 1 *26^0 = 0+1 = 1;
    
    for(int i = 0; i != m; i++){
        //第一次 A = 0*26+2;
        //第二次 A = 2*26+2;
        A = (d*A + (P[i] - 'a'));
        
        //第一次 st = 0*26+0
        //第二次 st = 0*26+1
        St = (d*St + (S[i] - 'a'));
        
    }
    
    //3. 獲取d^m-1值(因?yàn)榻?jīng)常要用d^m-1進(jìn)制值)
    int hValue = getMaxValue(m);
    
    //4.遍歷[0,n-m], 判斷模式串HashValue A是否和其他子串的HashValue 一致.
    //不一致則繼續(xù)求得下一個(gè)HashValue
    //如果一致則進(jìn)行二次確認(rèn)判斷,2個(gè)字符串是否真正相等.反正哈希值沖突導(dǎo)致錯(cuò)誤
    //注意細(xì)節(jié):
    //① 在進(jìn)入循環(huán)時(shí),就已經(jīng)得到子串的哈希值以及主串的[0,m)的哈希值,可以直接進(jìn)行第一輪比較;
    //② 哈希值相等后,再次用字符串進(jìn)行比較.防止哈希值沖突;
    //③ 如果不相等,利用在循環(huán)之前已經(jīng)計(jì)算好的st[0] 來(lái)計(jì)算后面的st[1];
    //④ 在對(duì)比過(guò)程,并不是一次性把所有的主串子串都求解好Hash值. 而是是借助s[i]來(lái)求解s[i+1] . 簡(jiǎn)單說(shuō)就是一邊比較哈希值,一邊計(jì)算哈希值;
    
    for(int i = 0; i <= n-m; i++){
        if(A == St)
            if(isMatch(S,i,P,m))
                //加1原因,從1開(kāi)始數(shù)
                return i+1;
        St = ((St - hValue*(S[i]-'a'))*d + (S[i+m]-'a'));
        
    }
    
    return -1;
}