字符串匹配問(wèn)題

給你兩個(gè)僅包含小寫字母的字符串：主串 S = "abcacabdc"、模式串 T = "abd"，請(qǐng)查找出模式串在主串第一次出現(xiàn)的位置。在這題中答案是 6。

備注：主串和模式串均為小寫字母且都是合法輸入，代碼中不用考慮字符串的異常情況。

BF算法

BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是將目標(biāo)串 S 的第一個(gè)字符與模式串 T 的第一個(gè)字符進(jìn)行匹配，若相等，則繼續(xù)比較 S 的第二個(gè)字符和 T 的第二個(gè)字符；若不相等，則比較 S 的第二個(gè)字符和 T 的第一個(gè)字符，依次比較下去，直到得出最后的匹配結(jié)果。BF算法是一種蠻力算法，時(shí)間復(fù)雜度為 O(m*n)。

思路：

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

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

3. 如果 j > T.length，說(shuō)明模式T中的每個(gè)字符串依次和主串S找中的一個(gè)連續(xù)字符序匹配成功，返回和模式T中第一個(gè)字符的字符在主串S中的序號(hào) (i-T.length); 否則匹配失敗,返回-1;

備注：字符串的下標(biāo)0中存儲(chǔ)的是字符的長(zhǎng)度。

代碼如下：

int getIndex_BF(String strOne, String strTwo){
    
    int i = 1;
    int j = 1;
    
    //判斷兩個(gè)字符串是否比到尾了
    while (i <= strOne[0] && j <= strTwo[0] ) {
        //比較兩個(gè)字符是否相等
        if (strOne[i] == strTwo[j]) {
            //相等則繼續(xù)比較下一個(gè)
            I++;
            j++;
        }
        else {
            //不相等則從主串此次比較的下個(gè)位置繼續(xù)比較
            i -= (j - 2);
            //模式串要從頭開始
            j = 1;
        }
    }
    //如果j大于模式串的長(zhǎng)度，說(shuō)明找到了模式串，位置在i-模式串長(zhǎng)度的地方
    if (j > strTwo[0]) {
        return i - strTwo[0];
    }
    return -1;
}

RK算法

RK 算法的全稱叫 Rabin-Karp 算法。它是由兩位發(fā)明者 Rabin 和 Karp 的名字來(lái)命名的算法，這個(gè)算法理解不算過(guò)于復(fù)雜，但是有一些編碼技巧在里面，可以讓我們學(xué)習(xí)。

在剛剛學(xué)習(xí)的BF算法中，如果模式串長(zhǎng)度為 m，主串長(zhǎng)度為 n，那在主串中就會(huì)有 n-m+1 個(gè)長(zhǎng)度為 m 的子串。我們只需要暴力地對(duì)比這 n-m+1 個(gè)子串與模式串，就可以找出主串與模式串匹配的子串。但是每次檢查主串的子串與模式串是否匹配, 需要依次比對(duì)每個(gè)字符, 所以BF算法的時(shí)間復(fù)雜度比較高，是O(n*m)。我們對(duì)BF的字符串匹配算法稍加改造，引入哈希算法，時(shí)間復(fù)雜度立刻就會(huì)降低。

RK 算法的思路是這樣的：我們通過(guò)哈希算法對(duì)主串中的 n-m+1 個(gè)子串分別求哈希值，然后逐個(gè)與模式串的哈希值比較大小。如果某個(gè)子串的哈希值與模式串相等，那就說(shuō)明對(duì)應(yīng)的子串和模式匹配了。

RK算法.png

在講思路前我先講下這里我使用的Hash算法：

• 計(jì)算字符串的（每個(gè)字符的Ascii碼值 - 'a'的Ascii碼值 + 1），我稱之為Value;
• 將每個(gè)Value相乘，得到字符串的Hash值。

這個(gè)Hash算法不太好，會(huì)出現(xiàn)哈希沖突。大家自己可以設(shè)計(jì)不會(huì)出現(xiàn)沖突又好計(jì)算的Hash算法，在這里提一下，使用26進(jìn)制Hash算法模式串一長(zhǎng)就會(huì)造成Hash值超過(guò)long long類型的最大值，所以它也可能出現(xiàn)哈希沖突。

時(shí)間復(fù)雜度：

• 使用不會(huì)沖突的算法：O(n)；
• 使用會(huì)沖突的的Hash算法：O(m+n)，但是平均復(fù)雜度比BF算法好。

RK算法思路：

1. 記錄兩個(gè)字符串的長(zhǎng)度；
2. 計(jì)算模式串的Hash值；
3. 依次計(jì)算出主串每個(gè)子串的Hash值，邊計(jì)算邊比較，不要全部計(jì)算好再比較；
4. 在計(jì)算新子串的Hash值時(shí)可以根據(jù)舊子串的Hash計(jì)算得出，減少重復(fù)計(jì)算；
5. Hash值相同需對(duì)比一下子串和模式串是否匹配（防止出現(xiàn)哈希沖突），匹配則返回index；
6. 如果沒(méi)有找到匹配的子串，則返回-1。

代碼如下：

//RK算法
int getIndex_RK(String strOne, String strTwo){
    
    //1、記錄兩個(gè)字符串的長(zhǎng)度
    int lengthOne = strOne[0];
    int lengthTwo = strTwo[0];
    
    //2、計(jì)算模式串的Hash值
    long long twoHashValue = 1;
    for (int i = 1; i <= lengthTwo; i++) {
        int value = strTwo[i] - 'a' + 1;
        twoHashValue *= value;
    }
    
    //3、依次計(jì)算出主串每個(gè)子串的Hash值，邊計(jì)算邊比較
    long long oneHashValue = 1;
    for (int i = 1; i <= lengthOne - lengthTwo + 1; i++) {
        if (i == 1) {
            for (int j = 1; j <= lengthTwo; j++) {
                int value = strOne[j] - 'a' + 1;
                oneHashValue *= value;
            }
        }
        else {
            //4、計(jì)算新子串的Hash值可以根據(jù)舊子串的Hash計(jì)算得出，減少重復(fù)計(jì)算
            int valueOld = (strOne[i - 1] - 'a' + 1);
            int valueNew = (strOne[i + lengthTwo - 1] - 'a' + 1);
            oneHashValue = oneHashValue / valueOld * valueNew;
        }
        //5、Hash值相同需對(duì)比一下子串和模式串是否匹配（防止出現(xiàn)哈希沖突），匹配則返回index
        if (oneHashValue == twoHashValue) {
            int isOK = isMatch(strOne, i, strTwo);
            if (isOK == 1) {
                return I;
            }
        }
    }
    //6、如果沒(méi)有找到匹配的子串，則返回-1
    return -1;
}

//判斷Hash值相等的字符串是否相等
int isMatch(String strOne, int index, String strTwo){
    
    for (int i = 1; i <= strTwo[0]; i++) {
        if (strOne[index + i - 1] != strTwo[i]) {
            return 0;
        }
    }
    return 1;
}

輔助代碼

#include "string.h"

#define OK    1
#define ERROR 0
typedef int Status;

#define MAX_SIZE 100
//定義串，0號(hào)單元存放串的長(zhǎng)度
typedef char String[MAX_SIZE +1];

//生成一個(gè)其值等于chars的串
Status assignStr(String str, char *chars){
    
    int length = (int)strlen(chars);
    if (length > MAX_SIZE) {
        return ERROR;
    }
    str[0] = length;
    for (int i = 1; i <= length; i++) {
        str[i] = chars[i - 1];
    }
    return OK;
}

//打印字符串
void printfStr(String str){
    
    for (int i = 1; i <= str[0]; i++) {
        printf("%c",str[I]);
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    
    char *charsOne = "ssadfaadfsa";
    String strOne;
    assignStr(strOne, charsOne);
    printf("主串為：");
    printfStr(strOne);
    
    char *charsTwo = "fsa";
    String strTwo;
    assignStr(strTwo, charsTwo);
    printf("模式串為：");
    printfStr(strTwo);
    
    printf("第一次出現(xiàn)模式串的索引位置為：\n");
    int indexBf = getIndex_BF(strOne, strTwo);
    printf("BF算法：%d\n",indexBf);
           
    int indexRk = getIndex_RK(strOne, strTwo);
    printf("RK算法：%d\n",indexRk);
    return 0;
}

執(zhí)行結(jié)果

用例1.png

用例2.png