/**
* 寻找字符串A中是否包含字符串B
* BF算法思想:a字符串从来i遍历,b字符串从j遍历
* a.(i + j) == b.j;则j ++;
* 一直到出现 a.(i + j) != b.j;这时就的让j=0, i + 1 了;
* 比如:a=ababcd;b=abc;
* 首先找a.(i+j)=a,b.j=a;然后j + 1;
* a.(i+j)=b,b.j=b;然后j + 1;
* a.(i+j)=a,b.j=c;不相等,则j=0,i+1;
* a.(i+j)=b,b.j=a;不相等,则j=0,i+1;
* a.(i+j)=a,b.j=a;j+1;
* ....
* j=2了.即:b字符串循环完了,并且a.(i+j)=b.j;
* 这时我们就找到了a字符串的字串b了,就可以退出所有循环.
* 当i循环完了,还未找到a.(i+j)=b.j;这时就说明未找到字串b
* @author xlaohe1
*
*/
public class BF {
public static void main(String[] args) {
//bfAlgorithm("abcdabcdabcdxefasabcdeeffe", "abcde");
bfAlgorithm2("abcdabcdabcdxefasabcdeeffe", "abcdeeffed");
}
static void bfAlgorithm2(String a, String b) {
if(b.length() > a.length()) {
System.out.println("not found");
return;
}
int j, i;
for(i = 0; i < a.length(); i ++) {
String na = a.substring(i);
//System.out.println(na);
if(na.length() == b.length()) {// 如果剩下未判断a字符长度等于b字符长度,就直接进行equlas
if(a.substring(i).equals(b)) {
System.out.println("found: i = " + i);
System.out.println(na);
break;
} else {
System.out.println("not found");
break;
}
}
for(j = 0; j < b.length(); j ++) {
if(a.charAt(i + j) != b.charAt(j)) break;// a字符串与b字符进行BF比较,如果不相等就结束循环
}
if(j == b.length()) {
System.out.println("found: i = " + i);
System.out.println(a.substring(i, b.length() + i));
break;
}
}
}
public static void bfAlgorithm(String a, String b) {
if(b.length() > a.length()) {
System.out.println("not found");
return;
}
int i = 0, j = 0;
while(j < b.length() && i < a.length()) {
if(a.charAt(i + j) != b.charAt(j)) {
i ++;
j = 0;
} else
j ++;
}
if(i == a.length()) {
System.out.println("not found");
} else {
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("i = " + i + " , j = " + j);
System.out.println(a.substring(i, i + j));
System.out.println(b.substring(0, j));
}
}
}
欢迎指正
分享到:
相关推荐
字符串模式匹配BF实验 字符串模式匹配BF实验 字符串模式匹配BF实验
第一部分、KMP算法初解 1、普通字符串匹配BF算法与KMP算法的时间复杂度比较 2、BF算法与KMP算法的区别 3、BF算法为什么要回溯 4、KMP 算法思想 5、next数组的含义 第二部分、next数组求法的来龙去脉与KMP算法的源码
字符串匹配算法(模式搜索 Pattern Search)的应用于包括但不限于:生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测、论文查重等等等等。字符串匹配算法,就是在一个字符串text中查找是否存在一...
字符串匹配算法理解(从BF算法到KMP算法) 暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符...
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
字符串处理- 单模式匹配- 朴素的字符串匹配算法(BF 算法).rar
课程的一次作业,分享一下。编程菜鸟,程序问题很多,仅供参考
BF/KMP/BM 字符串单模匹配算法, 用途广泛; BF/KMP/BM 字符串单模匹配算法, 用途广泛; BF/KMP/BM 字符串单模匹配算法, 用途广泛;
基于字符串模式匹配算法的病毒感染检测问题——C语言实现。
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
最简单的串匹配算法,主串和模式串相比较,若相等,继续逐个后续字符,否则从主串的一下个字符起再重新和模式的字符比较之.
主要讲述字符串匹配的BF算法,介绍算法之后,还分析了算法的时间性能。
第三节、第四节,我会讲两种多模式串匹配算法,也就是在一个串中同时查找多个串,它们分别是 Trie 树和AC 自动机。今天讲的两个算法中,RK 算法是 BF 算法
实现BF算法的改进算法:KMP算法和BM算法; 对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。 附件中 3.3.h BF算法代码 3.5.h KMP算法代码 3.12.h BM算法代码
给定一个文本,在该文本中查找并定位任意给定字符串 实现BF算法; 实现BF算法的改进算法:KMP算法和BM算法; 对上述三个算法进行时间复杂性分析,并设计时间程序验证分析结果。
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数: ...
若不相等,则从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;若S中的字符全部比较完毕,则匹配失败。这个算法称为朴素的模式匹配算法,简称BF...
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
linux c 查找 字符串 匹配 模式匹配 KMP BF