字符串匹配是計(jì)算機(jī)的基本任務(wù)之一。

舉例來(lái)說(shuō)，有一個(gè)字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一個(gè)字符串"ABCDABD"？

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

1.

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一個(gè)字符與搜索詞"ABCDABD"的第一個(gè)字符，進(jìn)行比較。因?yàn)锽與A不匹配，所以搜索詞后移一位。

2.

因?yàn)锽與A不匹配，搜索詞再往后移。

3.

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

4.

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

5.

直到字符串有一個(gè)字符，與搜索詞對(duì)應(yīng)的字符不相同為止。

6.

這時(shí)，最自然的反應(yīng)是，將搜索詞整個(gè)后移一位，再?gòu)念^逐個(gè)比較。這樣做雖然可行，但是效率很差，因?yàn)槟阋?搜索位置"移到已經(jīng)比較過(guò)的位置，重比一遍。

7.

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

8.

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

9.

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

　　移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值

因?yàn)?6 - 2 等于4，所以將搜索詞向后移動(dòng)4位。

10.

因?yàn)榭崭衽cＣ不匹配，搜索詞還要繼續(xù)往后移。這時(shí)，已匹配的字符數(shù)為2（"AB"），對(duì)應(yīng)的"部分匹配值"為0。所以，移動(dòng)位數(shù) = 2 - 0，結(jié)果為 2，于是將搜索詞向后移2位。

11.

因?yàn)榭崭衽cA不匹配，繼續(xù)后移一位。

12.

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

13.

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

14.

下面介紹《部分匹配表》是如何產(chǎn)生的。

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

15.

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

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

　?。?AB"的前綴為[A]，后綴為[B]，共有元素的長(zhǎng)度為0；

　　－　"ABC"的前綴為[A, AB]，后綴為[BC, C]，共有元素的長(zhǎng)度0；

　?。?ABCD"的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長(zhǎng)度為0；

　?。?ABCDA"的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為"A"，長(zhǎng)度為1；

　　－　"ABCDAB"的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為"AB"，長(zhǎng)度為2；

　?。?ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長(zhǎng)度為0。

16.

"部分匹配"的實(shí)質(zhì)是，有時(shí)候，字符串頭部和尾部會(huì)有重復(fù)。比如，"ABCDAB"之中有兩個(gè)"AB"，那么它的"部分匹配值"就是2（"AB"的長(zhǎng)度）。搜索詞移動(dòng)的時(shí)候，第一個(gè)"AB"向后移動(dòng)4位（字符串長(zhǎng)度-部分匹配值），就可以來(lái)到第二個(gè)"AB"的位置。

　　接下來(lái)，就是我自己對(duì)KMP算法的實(shí)現(xiàn)了。

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

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

　　2) 實(shí)現(xiàn)待搜索字符串在搜索過(guò)程中的指針的移動(dòng)問(wèn)題

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

　　接下來(lái)我就貼上我實(shí)現(xiàn)的代碼

/*
*用KMP算法實(shí)現(xiàn)字符串匹配搜索方法
*該程序?qū)崿F(xiàn)的功能是搜索本目錄下的所有文件的內(nèi)容是否與給定的
*字符串匹配，如果匹配，則輸出文件名：包含該字符串的行
*待搜索的目標(biāo)串搜索指針移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)部分匹配值
*/

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

#define KEYWORD_MAX_LENGTH 100      //設(shè)定搜索串的最大長(zhǎng)度

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

/*
*GetMatchValue:獲得字符串src的部分匹配值
*/
int GetMatchValue(char *src)
{
    int value = 0;
    int src_len = strlen(src);
    char *begin = src;    //初始化指向字符串第一個(gè)字符
    char *end = src + (src_len - 1);  //初始化指向字符串最后一個(gè)字符
    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);  //指向棧中最后一個(gè)元素
    int flag = 0;   //用一個(gè)標(biāo)志位來(lái)確定后綴棧中到最后一個(gè)元素都與前綴棧中的符號(hào)匹配
    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;   //第一個(gè)字符無(wú)前綴和后綴，所以為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)個(gè)字符
            dst[i+1] = '\0';    //注意字符串要以'/0'結(jié)尾
            table[i] = GetMatchValue(dst); 
            free((void*)dst);    
        }
    }
    return EXIT_SUCCESS;
}

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

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

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

    while(*p != '\0')   //直到搜索到目標(biāo)串的最后一個(gè)字符為止
    {
        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);  //放回搜索到的結(jié)果的數(shù)目
    Table_Print(search_str,kmp_table);
    printf("%s\n",dst_str);         //輸出待搜索的目標(biāo)串
    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;    //打印搜索串在目標(biāo)串中的位置
            before = record_position[i]+1;
            for(j=1;j<=num;j++)
                printf(" ");
            printf("*");
        }
        printf("\n");
    }
    
    return EXIT_SUCCESS;
}

　　測(cè)試的結(jié)果：

最新評(píng)論