简介
BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法。
主要思想
其主要思想为将目标串S(以下简称S)和模式串T(以下简称T)里的字符一一对比寻找(一般从第一个字符开始),如果相同,则比较下一个字符,如果不同,则从S的第二个字符与T的第一个字符开始比较,以此类推,直至最终得到结果。
如果可以在S中寻找到T,我们返回的是相匹配字符串中第一个字符在S串里的下标索引值;如果找不到,我们通常设置为返回-1。
时间复杂度
最理想的情况下 该算法的时间复杂度为O(n) 其中n为T串的长度,即一次遍历就在S中找到了T
最坏的情况下 该算法的时间复杂度为O(n*m) 其中 m 和 n
分别为 S 和 T 的长度,即前面每次匹配都不成功,直至到 S 的最后一个字符才与之匹配。
BF是一种简单暴力的算法,通过将两个字符串内的字符一一比较来得到最终结果。
因为是一种暴力算法,比较无脑,所以实现过程比较简单,逻辑也不难
适合应用于两个数据量较小的串之间的匹配。
但如果两个字符串S和T的数据量过大或者里面的字符比较相似时,由于程序要进行一一比较,所以运算会很多且复杂,效率不高。
源码
#include<stdio.h>
#include<string.h>
int BF(char a[100000],char b[100000])
{
int la=strlen(a); //获取a、b的长度
int lb=strlen(b);
printf("a b的长度分别为%d %d\n",la,lb);
int i=0; //i记录a的索引
int j=0; //j记录b的索引
while(i<la){
if(a[i]==b[j]&&j==lb-1){
return i-j; //返回第一个匹配成功的位置(此时的i并非a中第一个匹配成功的位置应该i-j)
}
else if(a[i]==b[j]&&j<lb-1){
i++;
j++;
}
else{
i=i-j+1; //此次匹配失败,i反回原位置并+1从下个位置开始重新匹配
j=0; //j重来
}
}
return -1; //没有找到
}
int main()
{
char a[100000];
char b[100000];
gets(a);
gets(b);
//puts(a);
//puts(b);
printf("%d\n",BF(a,b));
return 0;
}