幾種常見的字符串匹配算法 | 賴明星

lycbje 2014-03-25

展開全文

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

1. 樸素算法

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

#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次，所以它的時間復(fù)雜度為O(（N-M+1)*M)。

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

2. Rabin-Karp算法

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

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

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

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

Rabin-Karp算法的思想：

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

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

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

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

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

學(xué)習(xí)KMP算法請牢記兩點：

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