C語言實現(xiàn)字符串匹配KMP算法
字符串匹配是計算機的基本任務(wù)之一。
舉例來說，有一個字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一個字符串"ABCDABD"？
下面的的KMP算法的解釋步驟
1.
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一個字符與搜索詞"ABCDABD"的第一個字符，進(jìn)行比較。因為B與A不匹配，所以搜索詞后移一位。
2.
因為B與A不匹配，搜索詞再往后移。
3.
就這樣，直到字符串有一個字符，與搜索詞的第一個字符相同為止。
4.
接著比較字符串和搜索詞的下一個字符，還是相同。
5.
直到字符串有一個字符，與搜索詞對應(yīng)的字符不相同為止。
6.
這時，最自然的反應(yīng)是，將搜索詞整個后移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜索位置"移到已經(jīng)比較過的位置，重比一遍。
7.
一個基本事實是，當(dāng)空格與D不匹配時，你其實知道前面六個字符是"ABCDAB"。KMP算法的想法是，設(shè)法利用這個已知信息，不要把"搜索位置"移回已經(jīng)比較過的位置，繼續(xù)把它向后移，這樣就提高了效率。
8.
怎么做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產(chǎn)生的，后面再介紹，這里只要會用就可以了。
9.
已知空格與D不匹配時，前面六個字符"ABCDAB"是匹配的。查表可知，最后一個匹配字符B對應(yīng)的"部分匹配值"為2，因此按照下面的公式算出向后移動的位數(shù)：
移動位數(shù) = 已匹配的字符數(shù) - 對應(yīng)的部分匹配值
因為 6 - 2 等于4，所以將搜索詞向后移動4位。
10.
因為空格與Ｃ不匹配，搜索詞還要繼續(xù)往后移。這時，已匹配的字符數(shù)為2（"AB"），對應(yīng)的"部分匹配值"為0。所以，移動位數(shù) = 2 - 0，結(jié)果為 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位，這里就不再重復(fù)了。
14.
下面介紹《部分匹配表》是如何產(chǎn)生的。
首先，要了解兩個概念："前綴"和"后綴"。 "前綴"指除了最后一個字符以外，一個字符串的全部頭部組合；"后綴"指除了第一個字符以外，一個字符串的全部尾部組合。
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.
"部分匹配"的實質(zhì)是，有時候，字符串頭部和尾部會有重復(fù)。比如，"ABCDAB"之中有兩個"AB"，那么它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向后移動4位（字符串長度-部分匹配值），就可以來到第二個"AB"的位置。
接下來，就是我自己對KMP算法的實現(xiàn)了。
這個算法的實現(xiàn)主要包括了三個方面：
1) 求得我們用來搜索字符串的部分匹配值表
2) 實現(xiàn)待搜索字符串在搜索過程中的指針的移動問題
3) 如何定位我們搜索到的結(jié)果
接下來我就貼上我實現(xiàn)的代碼
/*
*用KMP算法實現(xiàn)字符串匹配搜索方法
*該程序?qū)崿F(xiàn)的功能是搜索本目錄下的所有文件的內(nèi)容是否與給定的
*字符串匹配，如果匹配，則輸出文件名：包含該字符串的行
*待搜索的目標(biāo)串搜索指針移動位數(shù) = 已匹配的字符數(shù) - 對應(yīng)部分匹配值
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define KEYWORD_MAX_LENGTH 100 //設(shè)定搜索串的最大長度
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; //搜索串的長度
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; //初始化指向字符串第一個字符
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; //用一個標(biā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; //第一個字符無前綴和后綴，所以為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'結(jié)尾
table[i] = GetMatchValue(dst);
free((void*)dst);
}
}
return EXIT_SUCCESS;
}
//打印搜索字符串對應(yīng)的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]); //左對齊輸出每個字符對應(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ù)
while(*p != '\0') //直到搜索到目標(biāo)串的最后一個字符為止
{
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;
}
測試的結(jié)果：
相關(guān)文章
這篇文章主要介紹了C++實現(xiàn)T型插補,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-10-10
C++基礎(chǔ)入門教程（一）：基礎(chǔ)知識大雜燴
這篇文章主要介紹了C++基礎(chǔ)入門教程（一）：基礎(chǔ)知識大雜燴,本文講解了注釋、頭文件、命名空間等內(nèi)容,需要的朋友可以參考下2014-11-11
這篇文章主要為大家詳細(xì)介紹了Qt實現(xiàn)簡易時鐘，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
最強的C語言筆記，此處對于C語言的基礎(chǔ)部分做一個簡要的介紹，作者實屬初學(xué)，寫博客也是作者學(xué)習(xí)的一個過程，若文中內(nèi)容有理解不到位或者有不當(dāng)之處，還請朋友們不吝指正2021-11-11
這篇文章主要介紹了C語言 位段的詳細(xì)介紹的相關(guān)資料,學(xué)習(xí)C語言基礎(chǔ)的朋友，可以參考本文，需要的朋友可以參考下2016-11-11
VC判斷進(jìn)程是否具有administrator權(quán)限的方法
這篇文章主要介紹了VC判斷進(jìn)程是否具有administrator權(quán)限的方法,在Windows應(yīng)用程序設(shè)計中具有一定的實用價值,需要的朋友可以參考下2014-10-10
今天小編就為大家分享一篇關(guān)于查找算法之二分查找的C++實現(xiàn)，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
OpenCV reshape函數(shù)實現(xiàn)矩陣元素序列化
reshape函數(shù)是OpenCV中一個很有用的函數(shù)，不僅可以改變矩陣的通道數(shù)，還可以對矩陣元素進(jìn)行序列化。本文將主要介紹如何通過reshape實現(xiàn)矩陣元素序列化，需要的小伙伴可以參考一下2021-12-12
這篇文章主要分下工的是18個C語言必背的經(jīng)典程序，下面文章我們就來看看實例，需要的小伙伴可以參考一下喲，希望對你有所幫助2021-10-10
二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多的數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變過來的。二叉樹的前，中，后3種遍歷方式，因為樹的定義本身就是遞歸定義的，所以采用遞歸的方法來實現(xiàn)是很簡單的2021-09-09