1. BF算法简介:
BF(Brute Force)算法是普通的模式匹配算法,又称为朴素匹配算法或蛮力算法,该算法最大缺点就是字符匹配失败指针就要回溯,所以性能很低。
2. BF算法思想:
BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。
3. Java实现:
// 朴素匹配算法
public class BruteForce {
/**
* @param mainStr 主串
* @param subStr 子串
* @return 字符串匹配成功起始位置
*/
public static int getMatchIndex(String mainStr, String subStr) {
int i = 0, j = 0;
while (i < mainStr.length()) {
if (mainStr.charAt(i) == subStr.charAt(j)) { // 两字母相等则继续
i++;
j++;
} else { // 两字母不等则角标后退重新开始匹配
i = i - j + 1; // i 回退到上次匹配首位的下一位
j = 0; // j 回退到子串的首位
}
if (j == subStr.length())
return i - j;
}
return -1;
}
public static void main(String[] args) {
System.out.println("匹配成功的位置为: " + getMatchIndex("god is a girl", "girl"));
}
}
注: 其实Java API中已经实现了字符串匹配这一算法,如: "abc".indexOf("bc") 将会返回1。这里仅仅是模拟该算法,仅供参考。
4. BF算法时间复杂度:
该算法最坏情况下要进行 M * ( N - M + 1) 次比较,时间复杂度为
O ( M * N )。
分享到:
相关推荐
《大话数据结构》———C语言简单实现KMP模式匹配算法
Android之大话设计模式——:抽象工厂模式借鉴.pdf
Android之大话设计模式——:抽象工厂模式参考.pdf
9.1 1分钟彻底理解指针的概念 9.2 大话C语言指针变量 9.3 C语言指针变量的运算 9.4 数组指针(指向数组的指针) 9.5 字符串指针(指向字符串的
数据结构与算法问题 讲解生动 数据结构不在
Android之大话设计模式:抽象工厂模式终稿.pdf
特别提醒:本文件为《大话数据分析:Tableau数据可视化实战》的数据集,并不是PDF书籍。
ZIP格式。算法与数据结构c与c++描述
数据结构与算法(大话设计模式)自己做的笔记
Java代码积累:并发 设计模式 数据结构 使用容器 实用 类 基础知识 并发性 演示线程的生命周期 生产者-消费者 设计模式参考《大话设计模式》 工厂简单模式 创造型模式 工厂方法模式 抽象工厂模式 原型模式 建造者...
大话数据结构 .pptx
基于《大话数据结构》进行数据结构的学习
引用于大话数据结构 有如图的T字符串和P字符串 匹配表(Partial Match Table) 也就KMP算法的核心 匹配表的第一步是拆分 分为 而对应的最大公共前后缀长度为 就是将拆分下来的字符串,进行前缀和后缀的匹配 例如a,...
大话Oracle RAC:集群、高可用性、备份与恢复(带目录清晰中文完整版)
查找算法,平衡二叉树,大话数据结构里面的。
大话Oracle RAC:集群、高可用性、备份与恢复。 此书被认为不可多得的好资料之一:大话Oracle RAC(PDF经典),看完之后深有感触,发出来共享一下。
《图解算法》、《大话数据结构》、《啊哈算法》 2:面试 《编程之美》、《剑指offer》、《编程珠玑》 3:编程语言 《数据结构与算法分析:Java语言描述》 4:闲暇阅读 《算法帝国》、《数学之美》、《算法之美》 5:...
对于b站王卓数据结构的整理,此笔记由一些ppt图片与教材中的概念组成,大家下载后可以对其中文字进行编辑,80%的文字可以修改。同时也参考大话数据结构里的一些话语
《大话数据结构》——C语言简单实现单链表结构及相关一些操作