我們應(yīng)該都使用過String.indexOf("xxx")方法來查找某個(gè)字符或字符串在String中的位置，這就是一個(gè)字符串的匹配問題。字符串匹配在很多場景中都有應(yīng)用，下面介紹的幾種算法，就是在不同場景下的解決方法。

字符串的存儲

數(shù)據(jù)存儲只有順序或鏈?zhǔn)絻煞N方式，首先字符串并不適合使用鏈?zhǔn)酱鎯?，因?yàn)樽址怯勺址M成的，如果每個(gè)結(jié)點(diǎn)僅存儲一個(gè)字符，會浪費(fèi)大量的空間，而如果每個(gè)結(jié)點(diǎn)存儲多個(gè)字符，那這個(gè)數(shù)量的選擇就十分關(guān)鍵，不同的情況下可能需要不同的數(shù)量，這樣一來變數(shù)太大，不夠靈活。

而使用順序存儲的話，就不會有以上問題，但數(shù)組也有一定的缺陷，數(shù)組是定長的，有可能字符串比數(shù)組小，也可能數(shù)組放不下字符串，比如最初短信只能發(fā)70個(gè)漢字，超過的部分就會被丟棄，后來則是自動(dòng)拆分成兩條短信。所以存儲字符串使用的數(shù)組一般會通過動(dòng)態(tài)分配來處理。

“暴力”匹配算法

我們要做的，就是從一個(gè)字符串中，尋找到目標(biāo)子串出現(xiàn)的位置，比如在“helloworld”中找到“l(fā)ow”出現(xiàn)的位置。“暴力”匹配算法就是我們最容易想到的方案，那就是用目標(biāo)子串和該字符串的每一位一一對比，第一個(gè)字符一致再比第二個(gè)，直到找到為止。這里我們以char數(shù)組來模擬String，找到第一個(gè)匹配目標(biāo)即可。示例代碼如下：

private  int indexOf(char[] origin, char[] target){
    int originLen = origin.length;
    int targetLen = target.length;

    if(originLen==0 || targetLen == 0 || originLen<targetLen){
        return -1;
    }

    if(origin == target) return 0;

    int i=0,j=0;
    while (i<originLen && j<targetLen) {
        if(origin[i] == target[j]){
            // 如果相同就一一比較
            i++;
            j++;
        }else{
            // 不相同，i指向上次匹配第一個(gè)字符的下一位，j清零
            i = i-j+1;
            j=0;
        }
    }

    if(j>targetLen-1) return i-targetLen;
    else return -1;
}

我們算下“暴力”匹配算法的時(shí)間復(fù)雜度，假設(shè)n是原字符串長度，m是目標(biāo)字符串長度，最好的情況是上來就匹配，也就是只走if語句，需要運(yùn)行m次，所以復(fù)雜度為O(1)。最壞的情況是，每次都先走if語句，到最后一位判斷時(shí)發(fā)現(xiàn)不匹配，然后else-if交替進(jìn)行，時(shí)間復(fù)雜度為O((n-m+1)*m)，這就好比是從字符串aaaaaaaaaab中查找ab，每次比對都發(fā)現(xiàn)第一個(gè)字符相同，但第二個(gè)字符不同。

在字符串比較短時(shí)，這個(gè)算法是可行的，但是當(dāng)字符串非常長時(shí)，它的效率就十分低了。

KMP匹配算法

“暴力”匹配算法的主要問題在于執(zhí)行else時(shí) i 的回溯。我們以在字符串abcdefg...中尋找abcdh為例，來說明以上算法的問題。

暴力匹配

上圖中，用灰線表示匹配成功，紅線表示匹配失敗?？梢园l(fā)現(xiàn)，因?yàn)?code>abcdh沒有重復(fù)字符，而abcd又在步驟①時(shí)都比較過了，它們分別對應(yīng)相等，所以第一個(gè)字符a不可能與后邊的bcd三個(gè)字符相等了，也就是說步驟②③④都是多余的。

當(dāng)然，字符不重復(fù)是特殊情況，下面我們看看字符有重復(fù)時(shí)的情況，以在字符串abcababc...中查找abcabd為例。

重復(fù)字符

首先，步驟②和③是可以省略的，而目標(biāo)串第一位的a和第四位一樣，第二位的b和第五位一樣，而第四位和第五位的a和b字符又已經(jīng)和原串比較過了，它們是相等的，也就是說前兩位的ab和原串第四位和第五位是分別相等的，因此步驟④和⑤也是可以省略的。

分析以上兩種情況，可以發(fā)現(xiàn)，無論是否有重復(fù)字符，i 的值都不需要回溯，也就是從頭到尾遍歷一次原串，就能完成匹配。KMP算法就是把以上思路轉(zhuǎn)為實(shí)現(xiàn)。

KMP算法的核心是計(jì)算出一個(gè)next數(shù)組，這個(gè)數(shù)組表示在暴力匹配算法中 j 的變化，也就是目標(biāo)串首字符與原串比較的位置，比如在字符不重復(fù)例子中，從步驟①直接到步驟⑤，j 的變化就是從0到3，而在字符重復(fù)的例子中，就是從0到5。這個(gè)next的計(jì)算遵循以下規(guī)則：

統(tǒng)計(jì)當(dāng)前字符下標(biāo) j 之前前綴和后綴最長連續(xù)重復(fù)字符數(shù)，把它的值當(dāng)做next數(shù)組對應(yīng)的數(shù)據(jù)值，沒有字符則值為-1。前綴指從前往后，不包含原串的所有子串，后綴是從后往前不包含原串的所有子串。

首先解釋一下前綴后綴，比如在字符串abcd中，a、ab、abc都是前綴，而d、cd、bcd都是后綴。同樣，我們分沒有重復(fù)和有重復(fù)來解釋這里next數(shù)組的計(jì)算方式。還是以abcdh為例，j 表示每個(gè)字符的下標(biāo)。

• 當(dāng)j=0時(shí)，j之前沒有字符，next[j]=-1;
• 當(dāng)j=1時(shí)，j之前只有字符a，沒有重復(fù)，所以next[j]=0;
• 當(dāng)j=2時(shí)，j之前有字符a和b，但是它們不相等，所以next[j]=0;
• 當(dāng)j=3時(shí)，j之前有a、b、c三個(gè)字符，也不重重，所以next[j]=0;
• ...

因?yàn)闆]有重復(fù)字符，所以next數(shù)組的最終值為-10000。

接下來我們看有重復(fù)字符的情況，以abcabd為例：

• 當(dāng)j=0時(shí)，j之前沒有字符，next[j]=-1;
• 當(dāng)j=1時(shí)，j之前只有字符a，沒有重復(fù)，所以next[j]=0;
• 當(dāng)j=2時(shí)，j之前有字符a和b，但是它們不相等，所以next[j]=0;
• 當(dāng)j=3時(shí)，j之前有a、b、c三個(gè)字符，也不重重，所以next[j]=0;
• 當(dāng)j=4時(shí)，j之前有abca四個(gè)字符，此時(shí)最前的字符a和最后的字符a相等，所以next[j]=1;
• 當(dāng)j=5時(shí)，j之前有abcab五個(gè)字符，此時(shí)最前的字符ab和最后的字符ab相等，所以next[j]=2;

所以next數(shù)組的最終值為-100012。

通過以上示例發(fā)現(xiàn)，next就是統(tǒng)計(jì)當(dāng)前位置之前連續(xù)重復(fù)的字符數(shù)量，所以代碼也就順理成章了，如下所示：

private int[] getNext(char[] target){
    int len = target.length;
    if(len==0){
        return new int[]{-1};
    }
    
    int[] next = new int[target.length];

    // j表示當(dāng)前位置，k表示子串需比較的第一位。
    int j=0,k=-1;
    next[0] = -1;
    while (j<len-1) {
        if(k==-1 || target[j]==target[k]){
            j++;
            k++;
            next[j]=k;
        }else{
            k=next[k];
        }
    }

    return next;
}

這里代碼對上述比較進(jìn)行了一次小的優(yōu)化。我們看分析abcabd時(shí)，當(dāng)j=4時(shí)，我們已經(jīng)判斷過前綴a和后綴a相等，那么當(dāng)j=5時(shí)，只需要再判斷前綴ab和后綴ab中的b是否相等就可以，因?yàn)閍已經(jīng)確認(rèn)是相等了。假如b是相等的，可以推算出next[5]=next[4]+1，也就是代碼中if語句的做法，這部分比較好理解。那假如是不同的呢，我們通過一個(gè)圖來說明，如下所示：

next值確定

next的值，也就是表示從0到j(luò)-1的所有字符中，前綴和后綴連續(xù)相同的最大值，我們把這個(gè)值記為k，那么k的值如果對應(yīng)到數(shù)組中的位置就恰好指向符合規(guī)則的前綴的下一位，如上圖所示。在②中，我們知道k=5，j=12，現(xiàn)在我們要計(jì)算j=13時(shí)next的值，也就是當(dāng) j 指向e時(shí)的值，我們發(fā)現(xiàn)②中k和j指向的值不再相等，意味著需要從新開始比較，但是我們卻不一定需要把 k 置為0，先看下圖，e對應(yīng)的最長子串應(yīng)該是abd：

e的最長子串

可以發(fā)現(xiàn)，①和③是有共性的，也就是它們的符合規(guī)則的子串前兩位是重合的，都是ab，而且①中k的位置，又正好是③中子串的最后一位，這意味著，我們只需要把原有的k，換成k=next[k]，就可以有效減少對比次數(shù)。當(dāng)然，有可能k向前移動(dòng)一次依然不符合，就可以再次向前移動(dòng)，直到從新開始。

有了next數(shù)組，我們就可以實(shí)現(xiàn)KMP算法了，代碼如下：

private int indexOfKMP(char[] origin, char[] target){
    int originLen = origin.length;
    int targetLen = target.length;

    if(originLen==0 || targetLen == 0 || originLen<targetLen){
        return -1;
    }

    if(origin == target) return 0;

    int i=0,j=0;
    int[] next = getNext(target);

    while (i<originLen && j<targetLen) {
        if(j==-1 || origin[i] == target[j]){
            // 如果相同就一一比較,j=0表示不需要比較
            i++;
            j++;
        }else{
            // j返回到合適的位置，i不再需要回溯
            j = next[j];
        }
    }

    if(j>targetLen-1) return i-targetLen;
    else return -1;
}

這段代碼和暴力匹配差別不大，主要是在if語句中增加了j==0的判斷，在else中減掉了 i 的回溯，從而大大提高效率。

KMP算法的最壞時(shí)間復(fù)雜度為O(n+m)，其中n表示原串長度，m表示目標(biāo)串的長度，它的最大優(yōu)勢在于把時(shí)間復(fù)雜度降低到了線性級別。但是在使用中，它的優(yōu)勢并不十分明顯，因?yàn)闃O少有需要在重復(fù)性很高的字符串中尋找重復(fù)性很高的子串，而且它還需要一個(gè)額外的數(shù)組來保存next。KMP算法的優(yōu)勢還在于不需要回退，所以它比較適合在長度不確定的輸入流中查找。Java的String類內(nèi)部indexOf方法使用的就是暴力匹配，可見KMP在一般場景下并不那么適用。

總結(jié)

除了以上算法之外，字符串匹配算法還有Boyer-Moore算法和Rabin-Karp算法等，這里就不再進(jìn)行研究了。感興趣的可以查閱《算法》一書?？傊谝话銏鼍跋挛覀兛梢允褂帽┝ζヅ渌惴?，而在超長的輸入流中則可以使用KMP算法，具體使用哪種還需要根據(jù)實(shí)際情況進(jìn)行評估。

以上涉及代碼均已上傳至我的github。

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。