1.简介
蛮力算法,比较简单的一种字符串匹配算法,在处理简单的数据时候就可以用,完全匹配,速度慢。
2.算法思想
将模式字符串与目标字符串逐个字符进行比较,将模式字符串的第一个字符与目标字符串的第一个字符串比较,如果相等就比较模式字符串的第二个字符和目标字符串的第二个字符,相等继续比较下一个,不相等的话就用模式字符串的第一个字符与目标字符串的第二个字符比较,依次比较。直到目标字符串的最后一个字符比较结束。
比如目标字符串为abcsadfcsafdsf,模式串为csaf,比较步骤如下:
1. c与a比较,不匹配
2. c与b比较,不匹配
3. c与c比较,匹配;s与s比较,匹配;a与a比较,匹配;f与d比较,不匹配
4. c与s比较,不匹配
5. c与a比较,不匹配
6. c与d比较,不匹配
7. c与f比较,不匹配
8. c与c比较,匹配; s与s比较,匹配; a与a比较,匹配; 与f比较,匹配 ------->成功
9. c与d比较,不匹配
10. c与s比较,不匹配
11. c与f比较,不匹配------>结束
3.算法实现
java代码
public class BFMain {
private int match(String match,String target){
char[] marArr = match.toCharArray();
char[] tarArr = target.toCharArray();
int i=0;
int j=0;
int index=-1;
while(j<tarArr.length){
if(marArr[i] == tarArr[j]){
i++;
j++;
}else{
j=j-i+1;
i=0;
}
if(i==marArr.length){
i=0;
index = j-1;
System.out.println(j-1);
}
}
return index;
}
public static void main(String[] args) {
BFMain m = new BFMain();
m.match("csaf", "abcsadfcsafdsfcsaf");
}
}
4.参考
http://www.cnblogs.com/coder2012/p/3279916.html
分享到:
相关推荐
带简单图形界面的暴力匹配算法的java实现。
字符串匹配算法(模式搜索 Pattern Search)的应用于包括但不...1、BF(Brute Force,暴力算法); 2、RK (Robin-Karp 算法); 3、KMP (D.E.Knuth、J.H.Morris、V.R.Pratt 算法); 4、哈希Hash与移动哈希算法;
暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个...
暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个...
LeetCode算法蛇形走位 This is a record of my exploring leetcode Overview Problem Solution no need to solve math BF findKth most common way std::reverse Finite State Machine brute force bfs when k=2 ...
串是由零个或多个字符组成的有限序列,又叫做字符串 串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的。...Brute-Force算法的基本思想: 从目标串s 的
暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个...
编程实现如下功能: 1、在实验六的基础上,实现串的Brute-Force模式匹配算法。 2、尝试实现串的KMP模式匹配算法。
虽然针对于KNN算法有各种各样的优化方式,但是这里讨论的重点是CUDA对KNN问题的优化,因此采用最基础(也是最暴力的)Brute Force算法——穷举法。当空间的维度不断提高时,其他算法的计算耗时也在不断提高,但是BF-...
BF(Brute Force)算法 RF(Rabin-Karp)算法 BM(Boyer-Moore)算法 KMP算法 多模式匹配算法(未完成) 字典树-Trie树; 有限自动机 树 前序,中序,后序,层序遍历; 倾斜二叉树; 算法 贪心 分治 回溯 动态规划 ...
BF/KMP/BM 字符串单模匹配算法, 用途广泛; BF/KMP/BM 字符串单模匹配算法, 用途广泛; BF/KMP/BM 字符串单模匹配算法, 用途广泛;
├─brute_force 串的匹配-BF算法 │ ├─expression_evaluation 栈-表达式计算 │ ├─lru LRU算法 │ ├─kmp KMP算法 ├─examination 题目 │ ├─队列 │ │ ├─moving_average_from_data_stream 数据流中的...
Brute Force,暴力匹配算法/朴素匹配算法 相关概念 主串(长度n) 模式串 (长度m) 子串 思想:主串中,从0 – n-m,依次匹配 最坏时间复杂度:O(n*m) 常用原因 模式串和主串不会太长,不匹配时可跳到下一位重新...