主串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)到末尾了崔赌，之后字符串長度都不夠意蛀，就不需要再比較了
                return NOT_FOUND;
        }
        i++; // 移動(dòng)字符開始的索引
    }
    return NOT_FOUND;
}

1.2 思路2

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

思路1中县钥，a指針都是依次增加的，所以a需要移動(dò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)到末尾了碗殷，之后字符串長度都不夠精绎，就不需要再比較了
                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ù)組長度
    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); // 獲取子串長度
    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減去匹配字符串的長度
    }
    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); // 獲取子串長度
    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減去匹配字符串的長度
    }
    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ù)可以被表示為：

這里只考慮小寫字母秕衙，我們有26個(gè)字母蠢甲，所以字母的進(jìn)制是二十六進(jìn)制，'a'的ASC碼為97据忘，如果直接用峡钓，很容易造成溢出問題，所以在計(jì)算Hash值時(shí)會(huì)減去'a'若河。比如"abc"就可以被表示為：

這里我們可以發(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：

我們假設(shè)d為使用的進(jìn)制未辆，m表示匹配串的長度，那么字符串的Hash值我們可以通過下面的公式進(jìn)行計(jì)算：

當(dāng)然我們使用取余也是可以的：

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); // 主串長度
    int m = (int)strlen(matchStr); // 子串長度
    
    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;
}