BF算法和KMP算法以及比较次数 （C语言）

BF算法和KMP算法以及比较次数 （C语言）

BF算法和KMP算法是字符串的两种主要的模式匹配算法

1.BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

如主串和子串的下标为i和j。如果两位相等即a[i]==b[j]， i++，j++，都后移一位。但是如果两位不相等，子串j会回到初始位置，而主串会回到上一次开始匹配的下一位，即i=i-j+1，再次匹配。

下列为BF算法：

//BF算法 
int BF(String S,String T){int i=1;// 主串的位置int j=1;// 模式串的位置int sum1=0;while(j<=T.length &&i<=S.length){if(T.ch[j-1]==S.ch[i-1]){// 当两个字符相同，就比较下一个++i;++j;sum1++;}else{i=i-j+2;// 一旦不匹配，i后退j=1;// j归1sum1++;//比较次数}}printf("BF比较%dn",sum1);if(j>T.length)return i-T.length;else return -1;}

next计算：

给大家示例：例如： 模式串 a b a a b c a c             next值 0 1 1 2 2 3 1 2

next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。 首先将前一位与其next值对应的内容进行比较， 如果相等，则该位的next值就是前一位的next值加上1； 如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值； 如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。

//得到next值 
void getnext(String T,int next[]){
// 求子串T的next函数值并存入数组nextint i=1;int j=0;next[1]=0;while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){++i;++j;next[i]=j;}else{j=next[j];}}
}

2.KMP算法：即是对BF算法的一种优化，所实现的功能是一样的。其优点是利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。j指针返回到对应的next值。

//KMP算法 
int  KMP(String S,String T,int next[]){int i=1;// 主串的位置int j=1;// 模式串的位置int sum2=0;while(j<=T.length&&i<=S.length){if(j==0||T.ch[j-1]==S.ch[i-1]){++i;++j;// 继续比较后继字符sum2++;}else {j=next[j];j回到指定位置sum2++;//比较次数}}printf("KMP比较%dn",sum2);if(j>T.length)return i-T.length;  // 匹配成功else return -1;}

完整的代码：

#include <stdio.h>
#include<string.h>
#define Maxsize 100
typedef struct Lnode{char ch[Maxsize];int length;
}String;
//得到next值 
void getnext(String T,int next[]){int i=1;int j=0;next[1]=0;while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){++i;++j;next[i]=j;}else{j=next[j];}}
}
//BF算法 
int BF(String S,String T){int i=1;int j=1;int sum1=0;while(j<=T.length &&i<=S.length){if(T.ch[j-1]==S.ch[i-1]){++i;++j;sum1++;}else{i=i-j+2;j=1;sum1++;}}printf("BF比较%dn",sum1);if(j>T.length)return i-T.length;else return -1;}
//KMP算法 
int  KMP(String S,String T,int next[]){int i=1;int j=1;int sum2=0;while(j<=T.length&&i<=S.length){if(j==0||T.ch[j-1]==S.ch[i-1]){++i;++j;sum2++;}else {j=next[j];sum2++;}}printf("KMP比较%dn",sum2);if(j>T.length)return i-T.length;else return -1;}
//主函数 
int main(){String T;String S;scanf("%s",&S.ch);scanf("%s",&T.ch);S.length=strlen(S.ch);T.length=strlen(T.ch);int next[Maxsize];getnext( T,next);int t=BF(S, T);int m= KMP( S, T, next);printf("BF在第%d位置n",t);printf("KMP在第%d位置n",m);return 0;
}