本文將介紹幾種常見的字符串匹配算法，大部分材料都是網(wǎng) 絡(luò)上收集而來(lái)。不過都經(jīng)過我審察學(xué)習(xí)過，保證是不錯(cuò)的學(xué)習(xí)素材。

1. 樸素算法

樸素算法是最簡(jiǎn)單的字符串匹配算法，也是人們接觸得最多的字符串匹配算法。代碼一看就懂，在此不在贅述。

#include<stdio.h>
#include<string.h>
void search(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++)
    {
        int j;

        /* For current index i, check for pattern match */
        for (j = 0; j < M; j++)
        {
            if (txt[i+j] != pat[j])
                break;
        }
        if (j == M)  // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
        {
           printf("Pattern found at index %d \n", i);
        }
    }
}

/* Driver program to test above function */
int main()
{
   char *txt = "AABAACAADAABAAABAA";
   char *pat = "AABA";
   search(pat, txt);
   getchar();
   return 0;
}

樸素算法有兩層循環(huán)，外層循環(huán)執(zhí)行N-M+1次，內(nèi)層循環(huán)執(zhí)行M次，所以它的時(shí)間復(fù)雜度為O(（N-M+1)*M)。

參考資料：http://www./searching-for-patterns-set-1-naive-pattern-searching/

2. Rabin-Karp算法

我們?cè)賮?lái)看一個(gè)時(shí)間復(fù)雜度為O(（N-M+1)*M)的字符串匹配算法，即Rabin-Karp算法。Rabin-Karp算法的預(yù)處理時(shí)間是O(m)， 匹配時(shí)間OO(（N-M+1)*M)，既然與樸素算法的匹配時(shí)間一樣，而且還多了一些預(yù)處理時(shí)間，那為什么我們 還要學(xué)習(xí)這個(gè)算法呢？

雖然Rain-Karp在最壞的情況下與樸素的世間復(fù)雜度一樣，但是實(shí)際應(yīng)用中往往比樸素算法快很多。而且該算法的 期望匹配時(shí)間是O(N+M)(參照《算法導(dǎo)論》)。

在樸素算法中，我們需要挨個(gè)比較所有字符，才知道目標(biāo)字符串中是否包含子串。那么， 是否有別的方法可以用來(lái)判斷目標(biāo)字符串是否包含子串呢？

答案是肯定的，確實(shí)存在一種更快的方法。為了避免挨個(gè)字符對(duì)目標(biāo)字符串和子串進(jìn)行比較， 我們可以嘗試一次性判斷兩者是否相等。因此，我們需要一個(gè)好的哈希函數(shù)（hash function）。 通過哈希函數(shù)，我們可以算出子串的哈希值，然后將它和目標(biāo)字符串中的子串的哈希值進(jìn)行比較。 這個(gè)新方法在速度上比暴力法有顯著提升。

Rabin-Karp算法的思想：

1. 假設(shè)子串的長(zhǎng)度為M,目標(biāo)字符串的長(zhǎng)度為N
2. 計(jì)算子串的hash值
3. 計(jì)算目標(biāo)字符串中每個(gè)長(zhǎng)度為M的子串的hash值（共需要計(jì)算N-M+1次）
4. 比較hash值
5. 如果hash值不同，字符串必然不匹配，如果hash值相同，還需要使用樸素算法再次判斷

為了快速的計(jì)算出目標(biāo)字符串中每一個(gè)子串的hash值，Rabin-Karp算法并不是對(duì)目標(biāo)字符串的 每一個(gè)長(zhǎng)度為M的子串都重新計(jì)算hash值，而是在前幾個(gè)字串的基礎(chǔ)之上， 計(jì)算下一個(gè)子串的 hash值，這就加快了hash之的計(jì)算速度，將樸素算法中的內(nèi)循環(huán)的世間復(fù)雜度從O(M)將到了O(1)。

關(guān)于hash函數(shù)的詳細(xì)內(nèi)容，可以參考這里或者《算法導(dǎo)論》。

下面是一個(gè)Rabin-Karp算法的實(shí)現(xiàn)：

/* Following program is a C implementation of the Rabin Karp Algorithm 
   given in the CLRS book */

#include<stdio.h>
#include<string.h>

// d is the number of characters in input alphabet
#define d 256 

/*  pat  -> pattern
    txt  -> text
    q    -> A prime number
*/
void search(char *pat, char *txt, int q)
{
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0;  // hash value for pattern
    int t = 0; // hash value for txt
    int h = 1;

    // The value of h would be "pow(d, M-1)%q"
    for (i = 0; i < M-1; i++)
        h = (h*d)%q;

    // Calculate the hash value of pattern and first window of text
    for (i = 0; i < M; i++)
    {
        p = (d*p + pat[i])%q;
        t = (d*t + txt[i])%q;
    }

    // Slide the pattern over text one by one 
    for (i = 0; i <= N - M; i++)
    {

        // Chaeck the hash values of current window of text and pattern
        // If the hash values match then only check for characters on by one
        if ( p == t )
        {
            /* Check for characters one by one */
            for (j = 0; j < M; j++)
            {
                if (txt[i+j] != pat[j])
                    break;
            }
            if (j == M)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
            {
                printf("Pattern found at index %d \n", i);
            }
        }

        // Calulate hash value for next window of text: Remove leading digit, 
        // add trailing digit           
        if ( i < N-M )
        {
            t = (d*(t - txt[i]*h) + txt[i+M])%q;

            // We might get negative value of t, converting it to positive
            if(t < 0) 
              t = (t + q); 
        }
    }
}

/* Driver program to test above function */
int main()
{
    char *txt = "GEEKS FOR GEEKS";
    char *pat = "GEEK";
    int q = 101;  // A prime number
    search(pat, txt, q);
    getchar();
    return 0;
}

參考資料：http://www./searching-for-patterns-set-3-rabin-karp-algorithm/

3. KMP算法

KMP算法是一個(gè)比較難以理解的算法。國(guó)內(nèi)非頂尖的大學(xué)數(shù)據(jù)結(jié)構(gòu)大都使用的是清華嚴(yán)老師的 《數(shù)據(jù)結(jié)構(gòu)》，這本書在第四章講到了KMP算法，我認(rèn)真看了兩遍沒有看懂。到現(xiàn)在我終于明白 了以后，我想說，真的是嚴(yán)老師實(shí)在講得太爛了。

KMP算法要講清楚很不容易，網(wǎng)絡(luò)上一搜一大堆材料，看完還是似懂非懂。我不準(zhǔn)備再講一遍， 我也不相信自己會(huì)講得比網(wǎng)絡(luò)上大多數(shù)文章講得好，在此給大家推薦阮一峰老師的《字符串匹配的KMP算法》。

學(xué)習(xí)KMP算法請(qǐng)牢記兩點(diǎn)：

1. KMP算法的思想就是，當(dāng)子串與目標(biāo)字符串不匹配時(shí)，其實(shí)你已經(jīng)知道了前面已經(jīng)匹配成功那 一部分的字符（包括子串與目標(biāo)字符串）。以阮一峰的文章為例，當(dāng)空格與D不匹配時(shí)，你其實(shí) 知道前面六個(gè)字符是"ABCDAB"。KMP算法的想法是，設(shè)法利用這個(gè)已知信息，不要把"搜索位置" 移回已經(jīng)比較過的位置，繼續(xù)把它向后移，這樣就提高了效率

   

2. 部分匹配表是模式自己與自己的匹配

下面推薦幾個(gè)KMP算法的練習(xí)：

4. Boyer-Moore算法

待補(bǔ)充。http://blog./52830/

5. Sunday算法

http://blog.163.com/yangfan876@126/blog/static/80612456201342205056344