动画：什么是 BF 算法 ？
16lz
2021-01-22
本文是图解 什么是 BF算法、KMP算法、BM算法 三部曲之一。
定义
Brute-Force算法，简称为 BF算法，是一种简单朴素的模式匹配算法，常用于在一个主串 S 内查找一个子串 T 的出现位置。
它的核心思想与操作是：
对于给定的主串 S 与子串 P ，主串 S 的长度为 N，子串 T 的长度为 M ；
首先，将 S[1] 和 T[1] 进行比较；
若相等，则再比较 S[2] 和 T[2] ，一直到 T[M] 为止；
若 S[1] 和 T[1] 不等，则 T 向右移动一个字符的位置，再依次进行比较；
动画演示
图片演示
代码描述
int index( String S, String T, int pos ){
int i = pos; // i 表示主串 S 中当前位置下标
int j = 1; // j 表示子串 T 中当前位置下标
while( i <= S[0] && j <= T[0] ){ // i 或 j 其中一个到达尾部则终止搜索
if( S[i] == T[i] ){ // 若相等则继续进行下一个元素匹配
i++;
j++;
}else { // 若匹配失败则 j 回溯到第一个元素重新匹配
i = i - j + 2; // 将 i 重新回溯到上次匹配首位的下一个元素
j = 1;
}
}
if( j > T[0] ){
return i - T[0];
}else {
return 0;
}
}
总结
BF算法 在主串和字串匹配失败时，主串进行的回溯操作会影响效率，回溯之后，主串与字串有些部分比较是没有必要的。这种简单的丢弃前面的匹配信息是 BF算法 之所以效率低效的一个重要因素。
KMP算法、BM算法 将在后续分别进行详细介绍，敬请关注。
更多相关文章
- 动画：七分钟理解什么是KMP算法
- 推荐一个项目：数据结构和算法必知必会的 50 个代码实现
- 这道算法题太简单？你忽略了时间复杂度的要求！
- 几道和「二叉树」有关的算法面试题
- 两分钟看完一道数学思想的算法题
- 链表算法面试问题？看我就够了！
- 算法面试经常需要你手写的三个排序算法（Python语言）
- 一道看完答案你会觉得很沙雕的「动态规划算法题」
- 几道和「堆栈、队列」有关的面试算法题