C說話完成字符串婚配KMP算法。本站提示廣大學習愛好者：（C說話完成字符串婚配KMP算法）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話完成字符串婚配KMP算法正文
字符串婚配是盤算機的根本義務之一。
舉例來講，有一個字符串"BBC ABCDAB ABCDABCDABDE"，我想曉得，外面能否包括另外一個字符串"ABCDABD"？
上面的的KMP算法的說明步調
1.
起首，字符串"BBC ABCDAB ABCDABCDABDE"的第一個字符與搜刮詞"ABCDABD"的第一個字符，停止比擬。由於B與A不婚配，所以搜刮詞後移一名。
2.
由於B與A不婚配，搜刮詞再往後移。
3.
就如許，直到字符串有一個字符，與搜刮詞的第一個字符雷同為止。
4.
接著比擬字符串和搜刮詞的下一個字符，照樣雷同。
5.
直到字符串有一個字符，與搜刮詞對應的字符不雷同為止。
6.
這時候，最天然的反響是，將搜刮詞全部後移一名，再從頭逐一比擬。如許做固然可行，然則效力很差，由於你要把"搜刮地位"移到曾經比擬過的地位，重比一遍。
7.
一個根本現實是，當空格與D不婚配時，你其實曉得後面六個字符是"ABCDAB"。KMP算法的設法主意是，想法應用這個已知信息，不要把"搜刮地位"移回曾經比擬過的地位，持續把它向後移，如許就進步了效力。
8.
怎樣做到這一點呢？可以針對搜刮詞，算出一張《部門婚配表》（Partial Match Table）。這張表是若何發生的，前面再引見，這裡只需會用便可以了。
9.
已知空格與D不婚配時，後面六個字符"ABCDAB"是婚配的。查表可知，最初一個婚配字符B對應的"部門婚配值"為2，是以依照上面的公式算出向後挪動的位數：
挪動位數 = 已婚配的字符數 - 對應的部門婚配值
由於 6 - 2 等於4，所以將搜刮詞向後挪動4位。
10.
由於空格與Ｃ不婚配，搜刮詞還要持續往後移。這時候，已婚配的字符數為2（"AB"），對應的"部門婚配值"為0。所以，挪動位數 = 2 - 0，成果為 2，因而將搜刮詞向後移2位。
11.
由於空格與A不婚配，持續後移一名。
12.
逐位比擬，直到發明C與D不婚配。因而，挪動位數 = 6 - 2，持續將搜刮詞向後挪動4位。
13.
逐位比擬，直到搜刮詞的最初一名，發明完整婚配，因而搜刮完成。假如還要持續搜刮（即找出全體婚配），挪動位數 = 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算法的完成了。
這個算法的完成重要包含了三個方面：
1) 求得我們用來搜刮字符串的部門婚配值表
2) 完成待搜刮字符串在搜刮進程中的指針的挪動成績
3) 若何定位我們搜刮到的成果
接上去我就貼上我完成的代碼
/*
*用KMP算法完成字符串婚配搜刮辦法
*該法式完成的功效是搜刮本目次下的一切文件的內容能否與給定的
*字符串婚配，假如婚配，則輸入文件名：包括該字符串的行
*待搜刮的目的串搜刮指針挪動位數 = 已婚配的字符數 - 對應部門婚配值
*/
#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;
}
/*
*創立搜刮字符串的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,打印出症結字串的地位信息,前往與症結字串婚配的數量
int Search_Keyword(char *dst_str,char *search_str)
{
char *p = dst_str;
char *q = search_str;
char *temp;
//創立症結字串的KMP表
Create_KMP_Table(search_str,kmp_table);
int count = 0; //記載如今曾經婚配的數量
int k = 0; //記載與症結字串婚配的字串的數量
int move = 0; //當字符串不婚配時，搜刮指針挪動的位數
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); //放回搜刮到的成果的數量
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;
}
測試的成果：
