c語言中關於使用BF-KMP演算法例項

直接上程式碼

複製程式碼 程式碼如下:

#define _CRT_SECURE_NO_WARNINGS

#include

#include

#include

#define MAX_SIZE 255 //定義字串的最大長度

typedef unsigned char SString[MAX_SIZE];//陣列第一個儲存長度

//BF

int BFMatch(char *s,char *p)

{

int i,j;

i=0;

while(i < strlen(s))

{

j=0;

while(s[i]==p[j]&&j < strlen(p))

{

i++;

j++;

}

if(j==strlen(p))

return i-strlen(p);

i=i-j+1; //指標i回溯

}

return -1;

}

//getNetx

void getNext(char *p,int *next)

{

int j,k;

next[0]=-1;

j=0;

k=-1;

while(j < strlen(p)-1)

{

if(k==-1||p[j]==p[k]) //匹配的情況下,p[j]==p[k]

{

j++;

k++;

next[j]=k;

}

else

{ //p[j]!=p[k]

k=next[k];

}

}

}

//KMP

int KMPMatch(char *s,char *p)

{

int next[100];

int i,j;

i=0;

j=0;

getNext(p,next);

while(i < strlen(s))

{

if(j==-1||s[i]==p[j])

{

i++;

j++;

}

else

{

j=next[j]; //消除了指標i的回溯

}

if(j==strlen(p))

{

return i-strlen(p);

}

}

return -1;

}

int main()

{

int a, b;

char s[MAX_SIZE], p[MAX_SIZE];

printf("請輸入模式串：");

scanf("%s", &s);

printf("請輸入子串：");

scanf("%s", &p);

a = BFMatch(s, p);

b = KMPMatch(s, p);

if(a != -1)

{

printf("使用BF演算法：%dn", a);

}

else

{

printf("未匹配n");

}

if(b != -1)

{

printf("使用KMP演算法：%dn", a);

}

else

{

printf("未匹配n");

}

system("pause");

}

結果

複製程式碼 程式碼如下:

請輸入模式串：lalalalalaaaa

請輸入子串：lalaa

使用BF演算法：6

使用KMP演算法：6

請按任意鍵繼續. . .