字符串匹配算法，是在實際工程中經(jīng)常遇到的問題，也是各大公司筆試面試的?？碱}目。此算法通常輸入為原字符串（string）和子串（pattern），要求返回子串在原字符串中首次出現(xiàn)的位置。比如原字符串為“ABCDEFG”，子串為“DEF”，則算法返回3。常見的算法包括：BF（Brute Force，暴力檢索）、RK（Robin-Karp，哈希檢索）、KMP（教科書上最常見算法）、BM（Boyer Moore）、Sunday等，下面詳細介紹。

1 BF算法：

暴力檢索法是最好想到的算法，也最好實現(xiàn)，在情況簡單的情況下可以直接使用：

首先將原字符串和子串左端對齊，逐一比較；如果第一個字符不能匹配，則子串向后移動一位繼續(xù)比較；如果第一個字符匹配，則繼續(xù)比較后續(xù)字符，直至全部匹配。
時間復(fù)雜度：O（MN）

2 RK算法：

RK算法是對BF算法的一個改進：在BF算法中，每一個字符都需要進行比較，并且當我們發(fā)現(xiàn)首字符匹配時仍然需要比較剩余的所有字符。而在RK算法中，就嘗試只進行一次比較來判定兩者是否相等。
RK算法也可以進行多模式匹配，在論文查重等實際應(yīng)用中一般都是使用此算法。

首先計算子串的HASH值，之后分別取原字符串中子串長度的字符串計算HASH值，比較兩者是否相等：如果HASH值不同，則兩者必定不匹配，如果相同，由于哈希沖突存在，也需要按照BF算法再次判定。
按照此例子，首先計算子串“DEF”HASH值為Hd，之后從原字符串中依次取長度為3的字符串“ABC”、“BCD”、“CDE”、“DEF”計算HASH值，分別為Ha、Hb、Hc、Hd，當Hd相等時，仍然要比較一次子串“DEF”和原字符串“DEF”是否一致。
時間復(fù)雜度：O（MN）（實際應(yīng)用中往往較快，期望時間為O（M+N））

3 KMP算法：

字符串匹配最經(jīng)典算法之一，各大教科書上的看家絕學(xué)，曾被投票選為當今世界最偉大的十大算法之一；但是晦澀難懂，并且十分難以實現(xiàn)，希望我下面的講解能讓你理解這個算法。
KMP算法在開始的時候，也是將原字符串和子串左端對齊，逐一比較，但是當出現(xiàn)不匹配的字符時，KMP算法不是向BF算法那樣向后移動一位，而是按照事先計算好的“部分匹配表”中記載的位數(shù)來移動，節(jié)省了大量時間。這里我借用一下阮一峰大神的例子來講解：

首先，原字符串和子串左端對齊，比較第一個字符，發(fā)現(xiàn)不相等，子串向后移動，直到子串的第一個字符能和原字符串匹配。

當A匹配上之后，接著匹配后續(xù)的字符，直至原字符串和子串出現(xiàn)不相等的字符為止。

此時如果按照BF算法計算，是將子串整體向后移動一位接著從頭比較；按照KMP算法的思想，既然已經(jīng)比較過了“ABCDAB”，就要利用這個信息；所以針對子串，計算出了“部分匹配表”如下（具體如何計算后面會說，這個先介紹整個流程）：

剛才已經(jīng)匹配的位數(shù)為6，最后一個匹配的字符為“B”，查表得知“B”對應(yīng)的部分匹配值為2，那么移動的位數(shù)按照如下公式計算：
移動位數(shù) = 已匹配的位數(shù) - 最后一個匹配字符的部分匹配值
那么6 - 2 = 4，子串向后移動4位，到下面這張圖：

因為空格和“C”不匹配，已匹配位數(shù)為2，“B”對應(yīng)部分匹配值為0，所以子串向后移動2-0=2位。

空格和“A”不匹配，已匹配位數(shù)為0，子串向后移動一位。

逐個比較，直到發(fā)現(xiàn)“C”與“D”不匹配，已匹配位數(shù)為6，“B”對應(yīng)部分匹配值為2，6-2=4，子串向后移動4位。

逐個比較，直到全部匹配，返回結(jié)果。
下面說明一下“部分匹配表”如何計算，“部分匹配值”是指字符串前綴和后綴所共有元素的長度。前綴是指除最后一個字符外，一個字符串全部頭部組合；后綴是指除第一個字符外，一個字符串全部尾部組合。以”ABCDABD”為例：
“AB”的前綴為[A]，后綴為[B]，共有元素的長度為0；
“ABC”的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度0；
“ABCD”的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為0；
“ABCDA”的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為”A”，長度為1；
“ABCDAB”的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為”AB”，長度為2；
“ABCDABD”的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0。
在計算“部分匹配表”時，一般使用DP（動態(tài)規(guī)劃）算法來計算（表示為next數(shù)組）：//這里我沒看懂，理論上不用DP直接搜也行啊

        int* next = new int[needle.length()];
        next[0] = 0;
        int k = 0;
        for (int i = 1; i < needle.length(); i++)
        {
            while (k > 0 && needle[i] != needle[k])
            {
                k = next[k - 1];
            }
            if (needle[i] == needle[k])
            {
                k++;
            }
            next[i] = k;
        }

時間復(fù)雜度：O（N）

4 BM算法：

在本科的時候，我一直認為KMP算法是最好的字符串匹配算法，直到后來我遇到了BM算法。BM算法的執(zhí)行效率要比KMP算法快3-5倍左右，并且十分容易理解。各種記事本的“查找”功能（CTRL + F）一般都是采用的此算法。
網(wǎng)上所有講述這個算法的帖子都是以傳統(tǒng)的“好字符規(guī)則”和“壞字符規(guī)則”來講述的，但是個人感覺其實這樣不容易理解，我總結(jié)了另外一套簡單的算法規(guī)則：
我們拿這個算法的發(fā)明人Moore教授的例子來講解：

首先，原字符串和子串左端對齊，但是從尾部開始比較，就是首先比較“S”和“E”，這是一個十分巧妙的做法，如果字符串不匹配的話，只需要這一次比較就可以確定。
在BM算法中，當每次發(fā)現(xiàn)當前字符不匹配的時候，我們就需要尋找一下子串中是否有這個字符；比如當前“S”和“E”不匹配，那我們需要尋找一下子串當中是否存在“S”。發(fā)現(xiàn)子串當中并不存在，那我們將子串整體向后移動到原字符串中“S”的下一個位置（但是如果子串中存在原字符串當前字符腫么辦呢，我們后面再說）：

我們接著從尾部開始比較，發(fā)現(xiàn)“P”和“E”不匹配，那我們查找一下子串當中是否存在“P”，發(fā)現(xiàn)存在，那我們就把子串移動到兩個“P”對齊的位置：

已然從尾部開始比較，“E”匹配，“L”匹配，“P”匹配，“M”匹配，“I”和“A”不匹配！那我們就接著尋找一下子串當前是否出現(xiàn)了原字符串中的字符，我們發(fā)現(xiàn)子串中第一個“E”和原字符串中的字符可以對應(yīng)，那直接將子串移動到兩個“E”對應(yīng)的位置：

接著從尾部比較，發(fā)現(xiàn)“P”和“E”不匹配，那么檢查一下子串當中是否出現(xiàn)了“P”，發(fā)現(xiàn)存在，那么移動子串到兩個“P”對應(yīng)：

從尾部開始，逐個匹配，發(fā)現(xiàn)全部能匹配上，匹配成功~
時間復(fù)雜度：最差情況O（MN），最好情況O（N）

int strStr(string haystack, string needle)
{
    if (needle.empty())
        return 0;
    if (haystack.size() < needle.size())
        return -1;

    const int s1 = haystack.size(), s2 = needle.size();
    int i1 = s2 - 1;
    int i2 = s2 - 1;

    while (i1 < s1)
    {
        int i3 = i1 - (s2 - 1 - i2);
        if (haystack[i3] != needle[i2])
        {
            int tmp = i2 + 1;
            for (int i = i2 - 1; i >= 0; i--)
            {
                if (haystack[i3] == needle[i])
                {
                    tmp = i2 - i;
                    break;
                }
            }
            i2 = s2 - 1;
            i1 += tmp;
        }
        else
        {
            i2--;
            if (i2 < 0)
                return i1 - (s2 - 1);
        }
    }
    return -1;
}

5 Sunday算法：

后來，我又發(fā)現(xiàn)了一種比BM算法還要快，而且更容易理解的算法，就是這個Sunday算法：

首先原字符串和子串左端對齊，發(fā)現(xiàn)“T”與“E”不匹配之后，檢測原字符串中下一個字符（在這個例子中是“IS”后面的那個空格）是否在子串中出現(xiàn)，如果出現(xiàn)移動子串將兩者對齊，如果沒有出現(xiàn)則直接將子串移動到下一個位置。這里空格沒有在子串中出現(xiàn)，移動子串到空格的下一個位置“A”：

發(fā)現(xiàn)“A”與“E”不匹配，但是原字符串中下一個字符“E”在子串中出現(xiàn)了，第一個字符和最后一個字符都有出現(xiàn)，那么首先移動子串靠后的字符與原字符串對齊：

發(fā)現(xiàn)空格和“E”不匹配，原字符串中下一個字符“空格”也沒有在子串中出現(xiàn)，所以直接移動子串到空格的下一個字符“E”：

這樣從頭開始逐個匹配，匹配成功！
時間復(fù)雜度：最差情況O（MN），最好情況O（N）

//實際我寫好像可以是o(M+N)啊。。

代碼粘一下：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
char a[10005],b[10005];//long a>long b
int c[30];//表示b串中存在的字母；不存在則為1，存在為最靠后的此字符距離尾部加一（要跳的地方） 
int la,lb;//字符串a(chǎn),b的長度 
int head;//當前搜索到的頭字符 
int main()
{
    scanf("%s",a);
    scanf("%s",b);//read in
    la=strlen(a);
    lb=strlen(b); 
    for(int i=0;i<=lb-1;i++)
        c[b[i]-'a'+1]=lb-i;//初始化c數(shù)組 
    for(int i=0;head<=la-1;)//i表示當前匹配長度 ,head指針跳到a尾時結(jié)束 
    {
        if(a[head+i]==b[i])
        {
            i++;//匹配則更新i值
            if(i==lb) //匹配到的長度等于b串長度 則成功 
            {
                printf("Yes");return 0;
            }
        }        
        else
        {
            if(c[a[head+lb]-'a'+1]!=0) head=head+c[a[head+lb]-'a'+1];//判斷是否出現(xiàn)
            else head=head+lb+2; //未出現(xiàn)，跳到下一個長度 
            i=0;//匹配值更新為0
        }         
    }
    printf("No");
    return 0;
}