`
xlaohe1
  • 浏览: 128771 次
  • 性别: Icon_minigender_1
  • 来自: 来处
社区版块
存档分类
最新评论

BF 字符串匹配

阅读更多

/**
 * 寻找字符串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));
		}
	}

}


欢迎指正
分享到:
评论

相关推荐

    C++ 字符串匹配

    在上面的代码中,我们首先定义了一个主串 `a` 和一个模式串 `b`,然后,我们使用 `BF` 函数来进行字符串匹配,并将结果输出到控制台。 其他字符串匹配算法 除了 Brute Force 算法外,还有许多其他的字符串匹配算法...

    Qt做的字符串匹配程序源代码

    本篇将详细介绍一个基于Qt框架实现的字符串匹配程序,该程序涵盖了多种经典的字符串匹配算法,包括BF算法(Brute Force)、KMP算法(Knuth-Morris-Pratt)以及BM算法(Boyer-Moore)。这些算法是计算机科学中的基础...

    实验三,微机软件实验3-字符串匹配实验 (2).rar

    - **位操作**:位操作可以用来加速某些字符串匹配算法,特别是在处理大量数据时,如Bitap算法(一种扩展的BF算法)。 - **数据结构**:如使用后缀数组或后缀树来实现高效的字符串查找。 实验中的代码和解说图片将...

    一种改进的字符串匹配算法

    在传统的字符串匹配算法如BF(Brute Force)算法中,一旦出现不匹配的情况,则需要回溯到前一个字符重新开始匹配,这导致了较高的时间复杂度。而KMP算法通过预先计算模式串的部分匹配表(next数组),避免了这种不必要...

    字符串匹配

    字符串匹配算法的发展见证了计算机科学领域的不断进步,从简单的BF算法到高效的BM算法和WM算法,每一步都体现了研究人员对算法性能的不懈追求。BM算法以其独特的后向匹配策略和跳跃机制,在单模式字符串匹配中树立了...

    GPU进行字符串匹配

    字符串匹配算法有多种,例如BF算法(Brute Force,暴力匹配算法)、KMP算法(Knuth-Morris-Pratt)、RK算法(Rabin-Karp算法)等。GPU通过SIMD(Single Instruction Multiple Data,单指令多数据)架构对图像数据...

    KMP(字符串匹配)算法总结

    ##### 1、普通字符串匹配BF算法与KMP算法的时间复杂度比较 KMP算法是一种高效的字符串匹配算法,它对基本的BF算法进行了优化。对于给定的原始串`S`和模式串`T`,目标是找到`T`在`S`中的位置。 **BF算法**(Brute-...

    32丨字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?1

    本节主要讨论了两种基本的字符串匹配算法:BF 算法(Brute Force 算法,又称暴力匹配算法)和 RK 算法(Rabin-Karp 算法),并探讨了如何利用哈希算法提高匹配效率。 BF 算法是最直观的字符串匹配方法,它通过逐一...

    C#,字符串匹配(模式搜索)BF(Brute Force)暴力算法的源代码

    字符串匹配算法(模式搜索 Pattern Search)的应用于包括但不限于:生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测、论文查重等等等等。字符串匹配算法,就是在一个字符串text中查找是否存在一...

    C语言:bf算法实现串匹配问题

    串匹配问题是计算机科学中一个基本问题,旨在寻找给定字符串在文本中的位置。BF算法、KMP算法和BM算法是解决串匹配问题的三种常见算法,本文将对这三种算法进行详细的分析和实现。 一、BF算法(Brute Force ...

    字符串处理- 单模式匹配- 朴素的字符串匹配算法(BF 算法).rar

    这里我们关注的是一个基础且重要的算法——朴素的字符串匹配算法,也称为BF算法(Brute Force 算法)。 BF算法由D.E.Knuth和J.H.Morris以及V.R.Pratt分别独立提出,因此也被称为KMP算法的前身。它的主要思想是通过...

    C++字符串匹配算法理解(从BF算法到KMP算法)

    字符串匹配算法理解(从BF算法到KMP算法) 暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符...

    c语言 字符串模式匹配BF实验

    **字符串模式匹配BF算法详解** 在信息技术领域,字符串模式匹配是一项基本且重要的任务,它用于在文本中查找是否存在特定的子串。BF算法,全称为Brute Force(暴力)算法,是最直观的一种字符串模式匹配算法。它...

    字符串匹配的KMP算法浅析

    KMP算法,全称Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,主要用于在一个文本字符串S内查找一个词W的出现位置。该算法由Donald Knuth、Vaughan Pratt和James H. Morris发明,因此得名。KMP算法的核心在于...

    基于字符串模式匹配算法的病毒感染检测问题_算法_数据结构_

    字符串模式匹配算法在此过程中扮演了核心角色,因为它可以高效地查找可能的病毒签名或恶意代码序列。本话题将深入探讨如何利用C语言实现基于字符串模式匹配算法的病毒感染检测。 首先,我们需要了解字符串模式匹配...

    基于GPU加速的并行字符串匹配算法.pdf

    经典的字符串匹配算法有BF算法、KMP算法、BM算法、BDM算法、Shift—A nd/Shift- Or算法等,这些算法都是基于滑动窗口方法,即以模式长度m为扫描窗口大小,在窗口中使用不同的扫描策略来进行匹配。 本文提出了一种...

    基于GPU加速的快速字符串匹配算法.pdf

    【基于GPU加速的快速字符串匹配算法】 在信息技术领域,字符串匹配是一个至关重要的任务,广泛应用于搜索引擎、网络安全、病毒检测和生物信息学等多个方面。传统的字符串匹配算法如KMP、Shift-And、BM和BDM等虽然...

    字符串匹配算法BFBMBMHBMHS分析归类.pdf

    本文主要探讨了两种经典的字符串匹配算法:BF(Brute Force,暴力匹配)算法和KMP(Knuth-Morris-Pratt)算法。 BF算法,又称为蛮力匹配,是最直观的一种字符串匹配方法。它的基本思想是从文本的起始位置开始,逐个...

Global site tag (gtag.js) - Google Analytics