[数据结构与算法]数据结构篇-----BF算法

最近复习的数据结构发现了许多新的知识点，特来上传到CSDN上总结一下，希望可以帮助到有需要的同学！

串的模式匹配就是在主串中查找与模式相匹配的子串，若匹配成功，确定相匹配的子串中的第一个字符在主串中出现的位置

BF算法即暴力破解法，设置指定主串中查找的起始位置pos，设置计数指针i=pos,j=1;分别指示主串和模式中当前正待比较的字符位置，将主串的第pos个字符和模式中的第一个字符比较，若相等，急需逐个比较后续逐个字符，若不相等，从主串的下一个字符(i=i-j+2)重新与模式串的第一个字符比较，，若主串的连续字符与模式串相等，则匹配成功，否则匹配失败，返回值为0.

C语言算法描述：

int? Index_BF(SString? S,SString? T,int? pos){

i=pos,j=1;

while(i<=S.length &&? j<=T.length){

if(S.ch[i]==T.ch[j]){

++i;++j;

}

else{i=i-j+2;j=1;}

if(j>T.length){

return i-T.length;

}

else return 0;

}

}

在匹配成功的情况下，考虑两种极端情况，即：

1、最好情况下，每趟不成功的匹配发生在与模式串的第一个字符与主串中相应字符的比较，平均时间复杂度为o(n+m)

2、最坏情况下，每趟不成功的匹配发生在与模式串的最后一个字符与主串中相应字符的比较，最坏情况下的平均时间复杂度为o（n×m）

OK，关于BF算法的总结就到这了。