C語(yǔ)言實(shí)現(xiàn)字符串匹配KMP算法
字符串匹配是計(jì)算機(jī)的基本任務(wù)之一。
舉例來(lái)說，有一個(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)比較過的位置，重比一遍。
7.
一個(gè)基本事實(shí)是，當(dāng)空格與D不匹配時(shí)，你其實(shí)知道前面六個(gè)字符是"ABCDAB"。KMP算法的想法是，設(shè)法利用這個(gè)已知信息，不要把"搜索位置"移回已經(jīng)比較過的位置，繼續(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)待搜索字符串在搜索過程中的指針的移動(dòng)問題
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é)果：
相關(guān)文章
這篇文章主要介紹了C++實(shí)現(xiàn)T型插補(bǔ),本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-10-10
C++基礎(chǔ)入門教程（一）：基礎(chǔ)知識(shí)大雜燴
這篇文章主要介紹了C++基礎(chǔ)入門教程（一）：基礎(chǔ)知識(shí)大雜燴,本文講解了注釋、頭文件、命名空間等內(nèi)容,需要的朋友可以參考下2014-11-11
Qt實(shí)現(xiàn)簡(jiǎn)易時(shí)鐘
這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)簡(jiǎn)易時(shí)鐘，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
C語(yǔ)言初識(shí)變量常量字符串轉(zhuǎn)義符及注釋方式簡(jiǎn)介
最強(qiáng)的C語(yǔ)言筆記，此處對(duì)于C語(yǔ)言的基礎(chǔ)部分做一個(gè)簡(jiǎn)要的介紹，作者實(shí)屬初學(xué)，寫博客也是作者學(xué)習(xí)的一個(gè)過程，若文中內(nèi)容有理解不到位或者有不當(dāng)之處，還請(qǐng)朋友們不吝指正2021-11-11
這篇文章主要介紹了C語(yǔ)言 位段的詳細(xì)介紹的相關(guān)資料,學(xué)習(xí)C語(yǔ)言基礎(chǔ)的朋友，可以參考本文，需要的朋友可以參考下2016-11-11
VC判斷進(jìn)程是否具有administrator權(quán)限的方法
這篇文章主要介紹了VC判斷進(jìn)程是否具有administrator權(quán)限的方法,在Windows應(yīng)用程序設(shè)計(jì)中具有一定的實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
今天小編就為大家分享一篇關(guān)于查找算法之二分查找的C++實(shí)現(xiàn)，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
OpenCV reshape函數(shù)實(shí)現(xiàn)矩陣元素序列化
reshape函數(shù)是OpenCV中一個(gè)很有用的函數(shù)，不僅可以改變矩陣的通道數(shù)，還可以對(duì)矩陣元素進(jìn)行序列化。本文將主要介紹如何通過reshape實(shí)現(xiàn)矩陣元素序列化，需要的小伙伴可以參考一下2021-12-12
這篇文章主要分下工的是18個(gè)C語(yǔ)言必背的經(jīng)典程序，下面文章我們就來(lái)看看實(shí)例，需要的小伙伴可以參考一下喲，希望對(duì)你有所幫助2021-10-10
通俗易懂講解C語(yǔ)言與Java中二叉樹的三種非遞歸遍歷方式
二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多的數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變過來(lái)的。二叉樹的前，中，后3種遍歷方式，因?yàn)闃涞亩x本身就是遞歸定義的，所以采用遞歸的方法來(lái)實(shí)現(xiàn)是很簡(jiǎn)單的2021-09-09