字符串匹配是計算機的基本任務之一。

舉例來說，有一個字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一個字符串"ABCDABD"？

下面的的KMP算法的解釋步驟

1.

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一個字符與搜索詞"ABCDABD"的第一個字符，進行比較。因為B與A不匹配，所以搜索詞后移一位。

2.

因為B與A不匹配，搜索詞再往后移。

3.

就這樣，直到字符串有一個字符，與搜索詞的第一個字符相同為止。

4.

接著比較字符串和搜索詞的下一個字符，還是相同。

5.

直到字符串有一個字符，與搜索詞對應的字符不相同為止。

6.

這時，最自然的反應是，將搜索詞整個后移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜索位置"移到已經比較過的位置，重比一遍。

7.

一個基本事實是，當空格與D不匹配時，你其實知道前面六個字符是"ABCDAB"。KMP算法的想法是，設法利用這個已知信息，不要把"搜索位置"移回已經比較過的位置，繼續(xù)把它向后移，這樣就提高了效率。

8.

怎么做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產生的，后面再介紹，這里只要會用就可以了。

9.

已知空格與D不匹配時，前面六個字符"ABCDAB"是匹配的。查表可知，最后一個匹配字符B對應的"部分匹配值"為2，因此按照下面的公式算出向后移動的位數(shù)：

　　移動位數(shù) = 已匹配的字符數(shù) - 對應的部分匹配值

因為 6 - 2 等于4，所以將搜索詞向后移動4位。

10.

因為空格與Ｃ不匹配，搜索詞還要繼續(xù)往后移。這時，已匹配的字符數(shù)為2（"AB"），對應的"部分匹配值"為0。所以，移動位數(shù) = 2 - 0，結果為 2，于是將搜索詞向后移2位。

11.

因為空格與A不匹配，繼續(xù)后移一位。

12.

逐位比較，直到發(fā)現(xiàn)C與D不匹配。于是，移動位數(shù) = 6 - 2，繼續(xù)將搜索詞向后移動4位。

13.

逐位比較，直到搜索詞的最后一位，發(fā)現(xiàn)完全匹配，于是搜索完成。如果還要繼續(xù)搜索（即找出全部匹配），移動位數(shù) = 7 - 0，再將搜索詞向后移動7位，這里就不再重復了。

14.

下面介紹《部分匹配表》是如何產生的。

首先，要了解兩個概念："前綴"和"后綴"。 "前綴"指除了最后一個字符以外，一個字符串的全部頭部組合；"后綴"指除了第一個字符以外，一個字符串的全部尾部組合。

15.

"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度。以"ABCDABD"為例，

　?。?A"的前綴和后綴都為空集，共有元素的長度為0；

　?。?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。

16.

"部分匹配"的實質是，有時候，字符串頭部和尾部會有重復。比如，"ABCDAB"之中有兩個"AB"，那么它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向后移動4位（字符串長度-部分匹配值），就可以來到第二個"AB"的位置。

　　接下來，就是我自己對KMP算法的實現(xiàn)了。

　　這個算法的實現(xiàn)主要包括了三個方面：

　　1) 求得我們用來搜索字符串的部分匹配值表

　　2) 實現(xiàn)待搜索字符串在搜索過程中的指針的移動問題

　　3) 如何定位我們搜索到的結果

　　接下來我就貼上我實現(xiàn)的代碼

/*
*用KMP算法實現(xiàn)字符串匹配搜索方法
*該程序實現(xiàn)的功能是搜索本目錄下的所有文件的內容是否與給定的
*字符串匹配，如果匹配，則輸出文件名：包含該字符串的行
*待搜索的目標串搜索指針移動位數(shù) = 已匹配的字符數(shù) - 對應部分匹配值
*/

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

#define KEYWORD_MAX_LENGTH 100      //設定搜索串的最大長度

int kmp_table[KEYWORD_MAX_LENGTH];  //為搜索串建立kmp表
char prefix_stack[KEYWORD_MAX_LENGTH]; //前綴表達式棧
char suffix_stack[KEYWORD_MAX_LENGTH]; //后綴表達式棧
int keyword_length = 0;  //搜索串的長度
int record_position[KEYWORD_MAX_LENGTH]; //記錄與關鍵字串匹配源串中的位置

/*
*GetMatchValue:獲得字符串src的部分匹配值
*/
int GetMatchValue(char *src)
{
    int value = 0;
    int src_len = strlen(src);
    char *begin = src;    //初始化指向字符串第一個字符
    char *end = src + (src_len - 1);  //初始化指向字符串最后一個字符
    int i = 0;
    for(i=0;i<(src_len-1);i++)
    {
        prefix_stack[i] = *begin;
        suffix_stack[i] = *end;
        begin++;
        end--;
    }
    char *p = prefix_stack;
    char *q = suffix_stack + (src_len - 2);  //指向棧中最后一個元素
    int flag = 0;   //用一個標志位來確定后綴棧中到最后一個元素都與前綴棧中的符號匹配
    while(q >= suffix_stack)
    {
        if(*p == *q)
        {
            value++;
            p++;
            flag=1;
        }
        else {
            flag = 0;
        }
        q--;
    }
    if(flag == 0) value = 0;
    return value;
}

/*
*創(chuàng)建搜索字符串的KMP表
*/
int Create_KMP_Table(char *str,int *table)
{
    int i;
    char *dst;
    keyword_length = strlen(str);
    for(i=0;i<keyword_length;i++)
    {
        if(i == 0) {
            table[i] = 0;   //第一個字符無前綴和后綴，所以為0
        }
        else {
            dst = (char*)malloc((i+2));
            if(dst == NULL)
            {
                printf("malloc space error!\n");
                return EXIT_FAILURE;
            }
            strncpy(dst,str,(i+1));   //匹配str的前(i+1)個字符
            dst[i+1] = '\0';    //注意字符串要以'/0'結尾
            table[i] = GetMatchValue(dst); 
            free((void*)dst);    
        }
    }
    return EXIT_SUCCESS;
}

//打印搜索字符串對應的KMP表
void Table_Print(char *str,int *table)
{
    int i;
    char c = *str;
    while(c != '\0')
    {
        printf("%-4c",c);        //左對齊輸出搜索字符串中的字符
        c = *++str;
    }
    printf("\n");
    for(i=0;i<keyword_length;i++)
    {
        printf("%-4d",table[i]); //左對齊輸出每個字符對應的部分匹配值
    }
    printf("\n");
}

//在目標串dst_str中搜索關鍵子串search_str,打印出關鍵字串的位置信息,返回與關鍵字串匹配的數(shù)目
int Search_Keyword(char *dst_str,char *search_str)
{
    char *p = dst_str;
    char *q = search_str;
    char *temp;

    //創(chuàng)建關鍵字串的KMP表    
    Create_KMP_Table(search_str,kmp_table);
    
    int count = 0;  //記錄現(xiàn)在已經匹配的數(shù)目
    int k = 0;     //記錄與關鍵字串匹配的字串的數(shù)目
    int move = 0;  //當字符串不匹配時，搜索指針移動的位數(shù)    

    while(*p != '\0')   //直到搜索到目標串的最后一個字符為止
    {
        temp = p;
        while(*q != '\0')
        {
            if(*q == *temp)
            {
                count++;
                temp++;
                q++;
            }
            else break;
        }
        
        if(count == 0)
            p++;
        else {
            if(count == keyword_length)
            {
                record_position[k++] = (temp-dst_str)-(keyword_length);
            }
            move = count - kmp_table[count-1];
            p += move;
        }

        count = 0;
        q = search_str;
    }
    return k;
}

int main(int argc,char **argv)
{
    char *search_str = argv[1];
    //char dst_str[] = "hello woshijpf woshijpf woshij woshijp woshijpf";
    char dst_str[] = "BBC ABCDAB ABCDABCDABDE";
    
    printf("Please input serach string and dst_string\n");
    if(search_str == NULL)
    {
        printf("Please input search string\n");
        return EXIT_FAILURE;
    }

    if(dst_str == NULL)
    {
        printf("Please input dst_string\n");
        return EXIT_FAILURE;
    }
    
    int result = Search_Keyword(dst_str,search_str);  //放回搜索到的結果的數(shù)目
    Table_Print(search_str,kmp_table);
    printf("%s\n",dst_str);         //輸出待搜索的目標串
    if(result == 0)
    {
        printf("Sorry!Don't find the string %s\n",search_str);
        return EXIT_SUCCESS;
    }
    else {
        int i,j,num;
        int before = 0;
        for(i=0;i<result;i++)
        {
            num = record_position[i] - before;    //打印搜索串在目標串中的位置
            before = record_position[i]+1;
            for(j=1;j<=num;j++)
                printf(" ");
            printf("*");
        }
        printf("\n");
    }
    
    return EXIT_SUCCESS;
}

　　測試的結果：

最新評論