1.BF算法

1.1 定義

BF算法，即暴風(fēng)算法，也有人稱為樸素算法、暴力算法。BF算法是一種做字符串匹配的算法。BF算法的思想是，將目標(biāo)串的第一個字符串與模式串的第一個字符串進(jìn)行比較，若相等，則繼續(xù)比較第二個字符串，直到將目標(biāo)串的字符串全部比較完。

1.2 代碼實現(xiàn)

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

圖1 .png

解析：根據(jù)BF算法，我們首先從模式串的第一個字符串與目標(biāo)串的第一個字符串進(jìn)行比較，發(fā)現(xiàn)相等，那么我們開始比較第二個字符串b，發(fā)現(xiàn)也想等，然后我們在比較第三個字符串發(fā)現(xiàn)不想等，所以，我們又需要重新將模式串的第一個字符串與目標(biāo)串的第二個字符串進(jìn)行比較，發(fā)現(xiàn)不相等，我們又接著將模式串的第一個字符串與目標(biāo)串的第三個字符串進(jìn)行比較，依次這樣進(jìn)行下去，直到在目標(biāo)串找到模式串出現(xiàn)的位置。

圖2.png

定義

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 40    /* 存儲空間初始分配量 */
typedef int Status;   /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElemType; /* ElemType類型根據(jù)實際情況而定，這里假設(shè)為int */
typedef char String[MAXSIZE+1]; /*  0號單元存放串的長度 */

思路:

1. 分別利用計數(shù)指針i和j指示主串S和模式T中當(dāng)前正待比較的字符位置,i初值為pos,j的初值為1;
2. 如果2個串均為比較到串尾,即i和j均小于等于S和T的長度時, 則循環(huán)執(zhí)行以下的操作:

• S[i]和T[j]比較,若相等,則i 和 j分別指示串中下一個位置,繼續(xù)比較后續(xù)的字符;
• 若不相等,指針后退重新開始匹配. 從主串的下一個字符串(i = i - j + 2)起再重新和模式第一個字符(j = 1)比較;

3. 如果j > T.length, 說明模式T中的每個字符串依次和主串S找中的一個連續(xù)字符序列相等,則匹配成功,返回和模式T中第一個字符的字符在主串S中的序號(i-T.length);否則匹配失敗,返回0;

int Index_BF(String S, String T,int pos){
    
    //i用于主串S中當(dāng)前位置下標(biāo)值，若pos不為1，則從pos位置開始匹配
    int i = pos;
    //j用于子串T中當(dāng)前位置下標(biāo)值
    int j = 1;
    
    //若i小于S的長度并且j小于T的長度時，循環(huán)繼續(xù)
    while (i <= S[0] && j <= T[0]) {
        
        //比較的2個字母相等,則繼續(xù)比較
        if (S[i] == T[j]) {
            I++;
            j++;
        }else
        {
            //不相等,則指針后退重新匹配
            
            //i 退回到上次匹配的首位的下一位;
            //加1,因為是子串的首位是1開始計算;
            //再加1的元素,從上次匹配的首位的下一位;
            i = i-j+2;
            
            //j 退回到子串T的首位
            j = 1;
        }}
    
    //如果j>T[0],則找到了匹配模式
    if (j > T[0]) {
        //i母串遍歷的位置 - 模式字符串長度 = index 位置
        return  i - T[0];
    }else{
        return -1;
    }
    
}

2.RK算法

2.1 哈希算法

Hash (哈希). 一般中文也翻譯做”散列”; 也可以直接音譯”哈?！? 散列在開發(fā)中是常見手段! 比如大家常用的MD5 算法就是哈希算法;哈希算法是將不同的字符組合能夠通過某種公式的計算映射成不同的數(shù)字! 哈希算法在安全方面應(yīng)用是非常多,一般體現(xiàn)在如下這幾個方面:
1.文件校驗；
2.數(shù)字簽名；
3.鑒權(quán)協(xié)議

2.2 定義

假設(shè)模式串與目標(biāo)串的前99個字符串都相等，而到了第100個字符串的時候發(fā)現(xiàn)不相等，這個時候如果用了BF算法，就會大大降低效率，于是，有了另一種算法RK算法。RK算法是由Rabin和Karp發(fā)明，因此該算法由二人首字母組成。該算法利用了hash思想，將字母換算成哈希值，即將[a·z]變成[0~25]的26進(jìn)制算法，類似十進(jìn)制的科學(xué)計算法。
譬如數(shù)字1863由以下科學(xué)計數(shù)法構(gòu)成：

1863 = 1* 10^3 + 8 * 10^2 + 6 * 10^1 + 3 * 10^0 ;

那么，bca的hash算法可以算成：

bca = 1 * 26^2 + 2 * 26^1 + 0 * 26^0 = 728 。

當(dāng)2個字符串算出來的hash值相等時，那么這2個字符串則有很大概率相等。

2.2 代碼實現(xiàn)

為了更好的推理RK算法，以數(shù)字為例會更好的理解。題目：它的全集是{0,1,2,3,4,5,6,7,8,9}.d = 10；模式串 p=123，主串 s=65127451234，求解字串A = 哈希值。

圖3.png

思路：將主串拆解成一個個子串與模式串進(jìn)行比較。

/*
 * 字符串匹配的RK算法
 * Author：Rabin & Karp
 * 若成功匹配返回主串中的偏移，否則返回-1
 */
//d 表示進(jìn)制
#define d 26

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

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