C语言实现字符串匹配KMP算法
字符串匹配是計算機的基本任務(wù)之一。
舉例來說，有一個字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一個字符串"ABCDABD"？
下面的的KMP算法的解釋步驟
1.
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一個字符與搜索詞"ABCDABD"的第一個字符，進行比較。因為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]; //前綴表達式棧 char suffix_stack[KEYWORD_MAX_LENGTH]; //后綴表達式棧 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é)果：
總結(jié)
以上是生活随笔為你收集整理的C语言实现字符串匹配KMP算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： brainfu*k语言执行
- 下一篇： Python的sys.stdout、sy