數(shù)據(jù)結(jié)構(gòu)與算法-字符串匹配與KMP

主串S："abcacabdc"，模式串T："abd"，請(qǐng)找出模式串在主串中第一次出現(xiàn)的位置。

提示：主串和模式串均為小寫字母且都是合法輸入。

1.1 思路1

  • 匹配肯定頭部要相等才開始比較后面的
  • 如果開始匹配，每一個(gè)字符都應(yīng)該相等，且不為結(jié)束符\0或0或NULL。
    • 如果匹配結(jié)束時(shí)，子串已經(jīng)到結(jié)束符，那說明和子串完全匹配

過程：

  1. abcacabdc 和 abd 匹配不上，移動(dòng)到下一個(gè)a開頭的子串
  2. abcacabdc 和 abd 匹配不上，移動(dòng)到下一個(gè)a開頭的子串
  3. abcacabdc 和 abd 匹配上了，返回abd開頭的索引
#define NOT_FOUND -1
int findStringInString(char *a, char *b) {
    if (!*a || !*b) return NOT_FOUND;
    int i = 0, j;
    char *p;
    while (a[i]) {
        if (a[i] == b[0]) {
            p = a + i; // 當(dāng)前字符串的開頭
            j = 1; // 頭已經(jīng)比較過了，從下一個(gè)位置開始比較
            while (p[j] && b[j] && p[j] == b[j]) // 一次比較
                j++;
            if (!b[j]) // 子串完全匹配
                return i;
            if (!p[j]) // 主串已經(jīng)到末尾了，之后字符串長(zhǎng)度都不夠，就不需要再比較了
                return NOT_FOUND;
        }
        i++; // 移動(dòng)字符開始的索引
    }
    return NOT_FOUND;
}

1.2 思路2

假設(shè)主串："abxabcabcaby"，子串："abcaby"。

思路1中，a指針都是依次增加的，所以a需要移動(dòng)n-k次，n為主串長(zhǎng)度，k為子串長(zhǎng)度。

參考每日氣溫 棧練習(xí)題 中題目2的思路2，跳躍對(duì)比的想法，在比較過程中如果出現(xiàn)了a開頭，我們就可以直接跳過中間不是a開頭的字符。

例如，abxabcabcaby中，abcabc不匹配之后，我們可以直接跳過bc來到下一個(gè)a。

int findStringInString2(char *a, char *b) {
    if (!*a || !*b) return NOT_FOUND;
    int i = 0, j, next = NOT_FOUND;
    char *p;
    while (a[i]) {
        if (a[i] == b[0]) {
            p = a + i; // 當(dāng)前字符串的開頭
            j = 1; // 頭已經(jīng)比較過了，從下一個(gè)位置開始比較
            while (p[j] && b[j]) { // 一次比較
                if (next == NOT_FOUND && p[j] == b[0]) { // 匹配過程中找到了下一個(gè)開頭
                    next = i + j;
                }
                if (p[j] != b[j]) break;
                j++;
            }
            if (!b[j]) // 子串完全匹配
                return i;
            if (!p[j]) // 主串已經(jīng)到末尾了，之后字符串長(zhǎng)度都不夠，就不需要再比較了
                return NOT_FOUND;
        }
        if (next != NOT_FOUND) {
            i = next;
            next = NOT_FOUND;
        } else {
            i++; // 移動(dòng)字符開始的索引
        }
    }
    return NOT_FOUND;
}

1.3 思路3

假設(shè)主串："abxabcabcaby"，子串："abcaby"。

思路2 abxabcabcaby 中，abcabc不匹配之后，我們可以直接跳過bc來到下一個(gè)a。

在匹配 abxabcabcaby 中，其實(shí)我們發(fā)現(xiàn)最后的c和子串的y不匹配，但是c之前的ab和aby中的ab是匹配過的，且ab在abcaby的前面也出現(xiàn)過，能否用這個(gè)思路來進(jìn)行跳躍對(duì)比呢？

顯然我們需要對(duì)我們的子串進(jìn)行處理，當(dāng)發(fā)生不匹配時(shí)，用來進(jìn)行跳躍。要怎么構(gòu)建這個(gè)跳躍信息呢？

以"abcaby"為例，重復(fù)的子串是ab。abcaby匹配abcabc時(shí)：

  • 當(dāng)前面字符均匹配，來到最后的y和c時(shí)發(fā)生不匹配。
  • 我們可以認(rèn)為y之前的ab已經(jīng)匹配過了，我們從abcaby跳過最前面的ab從c開始繼續(xù)進(jìn)行匹配。

也就是說，當(dāng)模式串存在重復(fù)子串時(shí)，我們可以回溯到重復(fù)子串之后一個(gè)位置繼續(xù)進(jìn)行匹配。

0 1 2 3 4 5 // 索引

a b c a b y // 模式串

0 0 0 1 2 0 // 回溯索引

第二次出現(xiàn)ab時(shí)，前一次他們出現(xiàn)的下一個(gè)位置是c。當(dāng)y不匹配時(shí)，我們看到前一個(gè)位置索引為2，正是我們子串c的索引值，然后繼續(xù)進(jìn)行比較。

1.3.1 構(gòu)建回溯數(shù)組

那么構(gòu)建這個(gè)數(shù)組的思路就明了了，即求出子串中重復(fù)子串的下一個(gè)位置。

我們用aabaabaaa進(jìn)行一次構(gòu)建來說明：

構(gòu)建回溯數(shù)組
int *GetNext(char *pattern){
    size_t length = strlen(pattern); // 獲取數(shù)組長(zhǎng)度
    int *res = (int *)malloc(sizeof(length) * length);
    res[0] = 0; // 第一個(gè)回溯索引為0
    for (int i = 1, j = 0; i < length;) {
        if (pattern[i] == pattern[j]) { // 匹配位置i和j的值相同，則res[i]等于j+1，i和j后移
            res[i] = j + 1;
            j++;
            i++;
        } else { // 匹配位置i和j的值不同
            if (j != 0) { // 還j不等于0，j等于前一個(gè)字符的回溯索引，重新比較
                j = res[j-1];
            } else {
                res[i] = 0; // j等于0，則res[i]填入0，i后移
                i++;
            }
        }
    }
    return res;
}
1.3.2 匹配過程

下面我們來說說比較問題：

這里我們用abxabcabcaby和abcaby進(jìn)行匹配。

匹配過程
int FindStringInString3(char *a, char *b){
    if (!*a || !*b) return NOT_FOUND;
    int length = (int)strlen(b); // 獲取子串長(zhǎng)度
    int *arr = GetNext(b, length); // 構(gòu)建回溯索引
    int i = 0, j = 0;
    while (a[i] && j < length) {
        if (a[i] == b[j]) { // 匹配位置i和j的值相同，i和j后移
            i++;
            j++;
        } else { // 匹配位置i和j的值不同
            if (j != 0) { // j不等于0，j等于前一個(gè)字符的回溯索引，重新比較
                j = arr[j-1];
            } else { // j等于0，i后移
                i++;
            }
        }
    }
    free(arr);
    if (j == length) { // 如果循環(huán)結(jié)束時(shí)是因?yàn)樽哟筋^了，說明匹配上了
        return i - length; // 子串的開始位置為i減去匹配字符串的長(zhǎng)度
    }
    return NOT_FOUND;
}
1.3.3 總結(jié)

這個(gè)算法其實(shí)就是著名的KMP算法。

核心思想：

若當(dāng)前位置不匹配，當(dāng)前位置前存在重復(fù)子串，則通過回溯可以跳過重復(fù)的子串繼續(xù)匹配，而不是從頭開始。

  • 這里相比于思路2，同時(shí)跳過了主串和模式串成功匹配的部分。
  • 1.3.2 匹配過程中的圖示8~10很好地體現(xiàn)了這個(gè)優(yōu)勢(shì)。

不管是構(gòu)建模式串的回溯數(shù)組還是匹配算法，其實(shí)兩個(gè)函數(shù)的處理是非常相似的。

int *GetNext(char *pattern, size_t length) {
    int *res = (int *)malloc(sizeof(int) * length);
    res[0] = 0; // 第一個(gè)回溯索引為0
    for (int i = 1, j = 0; i < length;) {
        if (pattern[i] == pattern[j]) { // 匹配位置i和j的值相同，則res[i]等于j+1，i和j后移
            res[i] = j + 1;
            j++;
            i++;
        } else { // 匹配位置i和j的值不同
            if (j != 0) { // j還不等于0，j等于前一個(gè)字符的回溯索引，重新比較
                j = res[j-1];
            } else {
                res[i] = 0; // j等于0，則res[i]填入0，i后移
                i++;
            }
        }
    }
    return res;
}

int FindStringInString3(char *a, char *b){
    if (!*a || !*b) return NOT_FOUND;
    int length = (int)strlen(b); // 獲取子串長(zhǎng)度
    int *arr = GetNext(b, length); // 構(gòu)建回溯索引
    int i = 0, j = 0;
    while (a[i] && j < length) {
        if (a[i] == b[j]) { // 匹配位置i和j的值相同，i和j后移
            i++;
            j++;
        } else { // 匹配位置i和j的值不同
            if (j != 0) { // j不等于0，j等于前一個(gè)字符的回溯索引，重新比較
                j = arr[j-1];
            } else { // j等于0，i后移
                i++;
            }
        }
    }
      free(arr);
    if (j == length) { // 如果循環(huán)結(jié)束時(shí)是因?yàn)樽哟筋^了，說明匹配上了
        return i - length; // 子串的開始位置為i減去匹配字符串的長(zhǎng)度
    }
    return NOT_FOUND;
}

int main(int argc, const char * argv[]) {
    char *a = "abxabcabcaby";
    char *b = "abcaby";
    int idx = findStringInString3(a, b);
    printf("%d\n", idx);
    return 0;
}

2. RK算法

該算法有幾點(diǎn)值得學(xué)習(xí)的地方：

  • 把字符串比較問題，轉(zhuǎn)換為了Hash值比較問題。
  • 利用前一個(gè)Hash值計(jì)算結(jié)果，輔助計(jì)算下一個(gè)Hash值。(可以算是動(dòng)態(tài)規(guī)劃)
  • 在比較的過程中，進(jìn)行判斷，同時(shí)解決Hash沖突問題。

2.1 字符串轉(zhuǎn)Hash值

在十進(jìn)制中一個(gè)數(shù)可以被表示為：
627 = 6 * 10^2 + 2 * 10^1 + 7 * 10^0
這里只考慮小寫字母，我們有26個(gè)字母，所以字母的進(jìn)制是二十六進(jìn)制，'a'的ASC碼為97，如果直接用，很容易造成溢出問題，所以在計(jì)算Hash值時(shí)會(huì)減去'a'。比如"abc"就可以被表示為：
abc = 0 * 26^2 + 1 * 26^1 + 3 * 26^0
這里我們可以發(fā)現(xiàn)一個(gè)Hash沖突問題，比如"abc"和"bc"的Hash值是一樣的，因?yàn)樽罡呶皇?code>0。

這里要解決Hash沖突有兩個(gè)辦法：

  • 使用更優(yōu)的Hash算法，比如我們不使用減去'a'，而是減去'a'-1。(a在最高位時(shí)不會(huì)為0)

  • 在發(fā)生沖突的時(shí)候，我們根據(jù)字符的起點(diǎn)，比較一下兩個(gè)字符串。

注意：Hash算法再牛逼，還是存在沖突的可能性。所以我們就算用了優(yōu)化的算法，最好也使用方法2再比較一次。

2.2 利用前一個(gè)結(jié)果計(jì)算下一個(gè)Hash值

我們還是以十進(jìn)制為例，主串6512，第一項(xiàng)為651，第二項(xiàng)為512：
\begin{equation}\begin{split} S_1 &= 6 * 10^2 + 5 * 10^1 + 1 * 10^0 \\ S_2 &= 5 * 10^2 + 1 * 10^1 + 2 * 10^0 \\ &= (6 * 10^2 + 5 * 10^1 + 1 * 10^0 - 6 * 10^2) * 10 + 2 * 10^0\\ &= (S_1 - 6 * 10^2) * 10 + 2 * 10^0 \end{split}\end{equation}
我們假設(shè)d為使用的進(jìn)制，m表示匹配串的長(zhǎng)度，那么字符串的Hash值我們可以通過下面的公式進(jìn)行計(jì)算：
str[i+1] = (str[i] - d^{m-1} * str[i]) * d + s[i+m]
當(dāng)然我們使用取余也是可以的：
str[i+1] = (str[i]\ \ mod\ \ d^{m-1}) * d + s[i+m]
RK算法實(shí)現(xiàn)：

#define NOT_FOUND -1

bool isMatch(char *mainStr, int i, char *matchStr, int m) {
    for (int j = 0; j < m; j++) {
        if (mainStr[i+j] != matchStr[j])
            return false;
    }
    return true;
}

int RK(char *mainStr, char *matchStr) {
    int d = 26; // 表示進(jìn)制
    int n = (int)strlen(mainStr); // 主串長(zhǎng)度
    int m = (int)strlen(matchStr); // 子串長(zhǎng)度
    
    unsigned int mainHash = 0; // 主串分解子串的哈希值
    unsigned int matchHash = 0; // 模式串的哈希值
    // 1.求得子串與主串中0~m字符串的哈希值[計(jì)算子串與主串0-m的哈希值]
    // 循環(huán)[0,m)獲取模式串A的HashValue以及主串第一個(gè)[0,m)的HashValue
    int offset = 'a' - 1; // a為最小值，保證a是最高位時(shí)，不會(huì)為0
    // 2.計(jì)算哈希值同時(shí)獲取d^m-1值(因?yàn)榻?jīng)常要用d^m-1進(jìn)制值)
    int dm1 = 0;
    for (int i = 0; i < m; i++) { // 小于m，不計(jì)算\0的值，數(shù)字會(huì)小一點(diǎn)
        matchHash = (d * matchHash + (matchStr[i] - offset));
        mainHash = (d * mainHash + (mainStr[i] - offset));
        dm1 = dm1 > 0 ? dm1 * d : 1;
    }
    
    // 3.遍歷比較哈希值
    for (int i = 0; i <= n-m; i++) {
        if (matchHash == mainHash // 判斷模式串哈希值是否和其他子串的哈希值一致
            && isMatch(mainStr, i, matchStr, m)) // 哈希值相等后，再次用字符串進(jìn)行比較，防止哈希值沖突
            return i;
        // 計(jì)算下一個(gè)子串的哈希值
        mainHash = (mainHash - (mainStr[i] - offset) * dm1) * d + mainStr[i+m] - offset;
//        mainHash = (mainHash % dm1) * d + mainStr[i+m] - offset; // 或者取余
    }
    return NOT_FOUND;
}

3. KMP改進(jìn)

對(duì)于aaaaab這個(gè)匹配串，next數(shù)組為0 1 2 3 4 0，但實(shí)際如果發(fā)生不匹配，不需要回溯前一個(gè)a，因?yàn)檫€是不匹配，應(yīng)該直接回溯到頭部。

這里修改一下KMP的實(shí)現(xiàn)，即現(xiàn)在next[j]對(duì)應(yīng)的是當(dāng)前不匹配時(shí)應(yīng)該回溯的索引，而不是通過next[j-1]獲取。同時(shí)頭部回溯索引使用-1，可以更方便判斷是否回到了頭部。

#define NOT_FOUND -1

int *GetNext(char *pattern, int length) {
    int *next = (int *)malloc(sizeof(int) * length);
    int i, j;
    j = next[0] = -1;
    i = 0;
    while (i < length-1) {
        // 當(dāng)因?yàn)榛厮輏<0時(shí)，說明一直不匹配，回溯到了頭部，當(dāng)前字符沒法匹配，所以i和j都進(jìn)行后移
        // j<0時(shí)，i++是為了開始下一個(gè)字符的比較(因?yàn)楫?dāng)前沒法再回溯了，說明這個(gè)字符沒法匹配)
        // j<0時(shí)，j++是為了使得j=0來到匹配串的開頭，開始下一輪的比較
        if (j < 0 || pattern[j] == pattern[i]) {
            i++;
            j++;
//            next[i] = j; // 未優(yōu)化
            // 如果當(dāng)前匹配，i和j后移之后還匹配，可以使用之前j的回溯值(更快回溯到頭部)
            // 為什么要使用next[j]，因?yàn)橹貜?fù)串回溯回去還是會(huì)不匹配，不如直接通過next[j]回溯到更前面
            // 如果當(dāng)前匹配，i和j后移之后不匹配，優(yōu)化前的策略得到回溯值
            next[i] = pattern[j] == pattern[i] ? next[j] : j;
        } else {
            // 當(dāng)前不匹配時(shí)，通過next[j]進(jìn)行回溯
            j = next[j];
        }
    }
    return next;
}

int FindStringInString(char *a, char *b) {
    if (!*a || !*b) return NOT_FOUND;
    int length = (int)strlen(b);
    int *next = GetNext(b, length); // 獲取next數(shù)組
    int i, j;
    i = j = 0;
    while (a[i] && j < length) {
        // 開始j = 0，所以直接比較字符是否相等
        // 當(dāng)因?yàn)榛厮輏<0時(shí)，說明一直不匹配，回溯到了頭部，當(dāng)前字符沒法匹配，所以i和j都進(jìn)行后移
        // j<0時(shí)，i++是為了開始下一個(gè)字符的比較(因?yàn)楫?dāng)前沒法再回溯了，說明這個(gè)字符沒法匹配)
        // j<0時(shí)，j++是為了使得j=0來到匹配串的開頭，開始下一輪的比較
        if (j < 0 || a[i] == b[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    free(next);
    if (j == length) {
        return i - length;
    }
    return NOT_FOUND;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容