字符串模式匹配bf算法

BF算法的实现一、基本思想：BF算法运用在文本搜索领域，具有简单、直接、无需对文本进行预处理等操作，因此被广泛的运用到多种文本检索系统中，但是BF算法实际上是一种暴力匹配的算法，算法的时间复杂度开销很大。

对于给定的原始字符串，当需要匹配的待匹配字符串时，从原始字符串的第一个位置开始匹配，观察是否匹配成功，如果失败，则将位置向后移动一位，继续匹配，依次类推，直到原始字符串最后位置前倒数查询字符串长度的位置截止。

原始的字符串是通过从文件中读入标准的字符串序列，而待查询的字符串是通过用户手动输入的一个字符串，实际匹配时通过观察待查询的子字符串是否在文件中的字符串序列中出现。

二、实现举例：文件中字符串序列为：当输入匹配模式词：Data结果为：三、小结：在某些文本检索领域中需要事先建立索引，然后才能进行快速查找。

但是，在某些应用中，这种建立索引的方法并不合适，文本过滤技术中，一般的文本只需要查询一次，这样就没有必要建立索引。

文本搜索技术具有广阔的应用前景，快速的文本检索技术是非常而且也是必须的。

BF算法是一种简单、直接、容易实现的字符串匹配算法，但是由于该算法本身所存在的局限性，相对于KMP和BM算法，还有很大的改进空间。

四、参考资料：刘挺，秦兵，张宇等.信息检索系统导论[M].北京：机械工业出版社，2008.附录：源代码/*** created by Jimmy* all right reserved* @date March 12th,2012*/package edu.zhang.index;import java.io.*;/*** The class used to use Pattern to match string* @author jimmy**/public class BruteForce {/*** the given string need to be matched*/private String stringOriginal="";/***substring to check if contained by a long string*/private String stringPattern="";/*** method used to do the matching* @author Jimmy*/public void patternMatch()throws Exception{BufferedReader binReadFromFile=new BufferedReader(newFileReader(System.getProperty("user.dir")+"/src/edu/zhang/index/BookInfo.txt"));String stringTemp="";while((stringTemp=binReadFromFile.readLine())!=null){stringOriginal+=stringTemp;}System.out.println("please input the string:");BufferedReader binFromTestString=new BufferedReader(new InputStreamReader(System.in));stringPattern=binFromTestString.readLine();//需要匹配的子字符串的长度int lengthOfPattern=stringPattern.length();//原始字符串的长度int lengthOfOrignal=stringOriginal.length();//用来表征是否出现了匹配的位置boolean signal=false;int index=1;for(int i=0;i<lengthOfOrignal-lengthOfPattern-1;i++){if(stringOriginal.substring(i,i+lengthOfPattern).equalsIgnoreCase(stringPattern)){System.out.println("第"+index+"次匹配成功,匹配的位置是："+i);index++;signal=true;}}if(!signal){System.out.println("没有出现匹配的字符串！");}}public static void main(String[] args)throws Exception { BruteForce bruteforce=new BruteForce();bruteforce.patternMatch();}}。

竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告篇一：串的模式匹配算法串的匹配算法——bruteForce(bF)算法匹配模式的定义设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。

通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。

模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。

bF算法brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。

以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。

实现代码如下：/*返回子串T在主串s中第pos个字符之后的位置。

若不存在，则函数返回值为0./*T非空。

intindex(strings,stringT,intpos){inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1；}if(j>T[0])returni-T[0];elsereturn0;}}bF算法的时间复杂度若n为主串长度，m为子串长度则最好的情况是：一配就中，只比较了m次。

最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m).篇二：数据结构实验报告-串实验四串【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：bF和Kmp。

3、了解串的应用。

【实验学时】2学时【实验预习】回答以下问题：1、串和子串的定义串的定义：串是由零个或多个任意字符组成的有限序列。

BF算法KMP算法BM算法BF算法（Brute-Force算法）是一种简单直接的字符串匹配算法。

它的基本思想是从主串的第一个字符开始，逐个与模式串的字符进行比较，如果匹配失败，则主串的指针向右移动一位，继续从下一个字符开始匹配。

重复这个过程，直到找到匹配的子串或者主串遍历完毕。

BF算法的时间复杂度是O(n*m)，其中n和m分别是主串和模式串的长度。

当模式串较长时，算法的效率较低。

但是BF算法的实现简单，易于理解，对于较短的模式串和主串，仍然是一种可行的匹配算法。

KMP算法（Knuth-Morris-Pratt算法）是一种改进的字符串匹配算法，它利用了模式串内部的信息，避免了不必要的比较。

KMP算法引入了一个next数组，用于记录模式串中每个位置对应的最长可匹配前缀子串的长度。

KMP算法的基本思想是，当匹配失败时，不是简单地将主串指针右移一位，而是利用next数组将模式串的指针向右移动若干位，使得主串和模式串中已经匹配的部分保持一致，减少比较次数。

通过预处理模式串，计算出next数组，可以在O(n+m)的时间复杂度内完成匹配。

BM算法（Boyer-Moore算法）是一种高效的字符串匹配算法，它结合了坏字符规则和好后缀规则。

BM算法从模式串的末尾开始匹配，根据坏字符规则，如果在匹配过程中发现了不匹配的字符，可以直接将模式串向右滑动到该字符在模式串中最右出现的位置。

BM算法还利用了好后缀规则，当发现坏字符后，可以根据好后缀的位置和模式串的后缀子串进行匹配，从而减少不必要的比较。

通过预处理模式串，计算出坏字符规则和好后缀规则对应的滑动距离，可以在最坏情况下实现O(n/m)的时间复杂度。

总结来说，BF算法是一种简单直接的字符串匹配算法，适用于较短的模式串和主串；KMP算法通过预处理模式串，利用next数组减少比较次数，提高了匹配效率；BM算法结合了坏字符规则和好后缀规则，利用了更多的信息，是一种高效的字符串匹配算法。

Boyer-Moore算法Boyer-Moore算法（简称BM算法）是一种高效的字符串匹配算法，由Robert S. Boyer和J Strother Moore于1977年提出。

相比于其他字符串匹配算法，如Brute-Force算法和KMP算法，BM算法在处理大型文本的匹配问题时具有较低的时间复杂度。

1. 算法原理BM算法的核心思想是从待匹配的字符串的末尾进行比较，而不是从开头。

具体来说，算法首先获取模式串（待搜索的子串）的最后一个字符，然后在待匹配的字符串中以模式串的长度为步长，从后往前进行比较。

如果比较的过程中发现存在不匹配的字符，算法会根据预处理的规则跳过一定范围的字符，从而实现快速的搜索。

而将模式串与待匹配的字符串进行比较的过程中，算法会根据预处理的规则将模式串向后移动一定的位置，以加快搜索的速度。

2. 算法流程BM算法的主要流程可以概括为以下几个步骤：1.预处理模式串：–建立一个坏字符规则表，记录每个字符在模式串中最右出现的位置。

–建立好后缀规则表，记录每个后缀子串在模式串中的出现位置。

2.匹配过程：–从待匹配字符串的末尾与模式串的末尾开始比较。

–如果遇到坏字符（即不匹配的字符），根据坏字符规则表和好后缀规则表进行移动。

–当模式串完全匹配，则表示找到了一个匹配的字符串。

3. 算法优势BM算法在字符串匹配问题中具有较高的效率，其优势主要体现在以下几个方面：•坏字符规则表：BM算法通过预处理模式串，建立坏字符规则表，从而实现在找到不匹配的字符时能够快速将模式串右移，从而跳过一定范围的字符。

这种方式可以大幅减少比较的次数，提高搜索效率。

•好后缀规则表：BM算法还通过预处理模式串，建立好后缀规则表。

当发现不匹配的字符时，算法会根据好后缀规则表的信息将模式串向后移动一定位置，以加快搜索速度。

•时间复杂度低：相比于Brute-Force算法和KMP算法，BM算法在处理大型文本的匹配问题时具有较低的时间复杂度。

字符串匹配算法详解(下)字符串匹配算法详解(上)介绍了BF算法和KMP算法，这一篇接着来介绍Horspool算法和BM算法。

其中Horspool算法相当于是BM算法的特例，或者说是简化版的BM算法。

算法三：Horspool算法Horspool是后缀搜索，有点创新啊，大家都从左往右匹配，它反着来。

也就是搜索已读入文本中是否含有模式串的后缀；如果有，是多长，显然，当后缀长度等于模式串的长度时，我们就找到了一个匹配。

Horspool算法思想：模式串从右向左进行匹配。

对于每个文本搜索窗口，将窗口内的最后一个字符（C）与模式串的最后一个字符进行比较。

如果相等，则继续从后向前验证其他字符，直到完全相等或者某个字符不匹配。

然后，无论匹配与否，都将根据在模式串的下一个出现位置将窗口向右移动。

模式串与文本串口匹配时，模式串的整体挪动，是从左往右，但是，每次挪动后，从模式串的最后一个字符从右往左进行匹配。

下面我们来看一个实例：加上匹配串和模式串如下：匹配串：abcbcsdLinac-codecbcac模式串：cbcac首先从右向左进行匹配，c与c匹配成功，接着第二个字符b与a，匹配失败（失配位置为3）。

于是，从模式串当前位置往左寻找匹配失败的那个字符，也即在模式串中寻找字符b上一次出现的位置(注意这里的“上一次”是指在模式串中从当前失配位置往左找到的第一个与失配位置相同的字符)；结果我们在模式串中找到了字符b，其位置为1，那么就将模式串整体往右挪动，把刚才找到的字符b与之前与匹配串中失配的字符b 对齐。

总共移动了多少位呢？移动了（3-1）位。

匹配串：abcbcsdLibac-codecbcac模式串：? cbcac模式串整体挪动到b处对齐后，再从右向左开始匹配，此时发现其第一个需要匹配的字符d与c就匹配失败（失配位置为4），尼玛，坑爹啊！那接下来怎么办？当然是跟上一步的方法一样，在模式串中去找失配的那个字符d，如果在模式串中找到了d，将模式串平移，使其d字符与匹配串的d对齐。

Brute-Force算法
Brute-Force算法简称BF算法:也称简单匹配算法，其基本思路是：从目标串s=”s0s1…sn-1”的第一个字符开始和模式串t=”t0t1…tm-1”中的第一个字符比较，若相等，则继续逐个比较后续字符，否则，从目标串s的第2个字符开始重新与模式串t的第一个字符进行比较，依次类推，若从模式串s的第i个字
符开始，每个字符依次和目标串t中的对应字符相等，则匹配成功，该算法返回i;否则匹配失败，返回-1. Java代码
1.private static int bruteforce(String source, String sub) {
2.int j = 0, i = 0;
3.int index = -1;
4.while (i < source.length() && j < sub.length()) {
5.if (source.charAt(i) == sub.charAt(j)) {
6.i++;
7.j++;
8.} else {
9.//使i回退到下一个字符，应为子串的前面j向可能匹配成功，而第j+1项失败，所以i=i-j+1
10.i = i - j + 1;
11.j = 0;
12.}
13.if (j == sub.length()) {
14.index = i - sub.length();
15.} else {
16.index = -1;
17.}
18.}
19.return index;
20.}。

BF算法（模式匹配）BF算法（Brute-Force算法）⼀种简单的模式匹配算法，⽬的是寻找模式串p是否在⽬标串s中有出现。

思想：先从第⼀个字符开始匹配，如果p[j]==s[i]，那么继续向下⽐较，⼀旦不相等，即回溯到⽬标串的下⼀个字符，重复⼯作。

成功条件：当循环结束时，判断j的值与模式串p的长度是否相等，如果相等，说明匹配成功到了模式p的最后⼀个字符。

返回值：返回模式串在⽬标串中出现的位置。

具体实现如下：#include <iostream>#include <string>using namespace std;int index(string s,string p){int i=0,j,k;while (i<s.length()){for (j=i,k=0;j<s.length() && k<p.length()&& s[j]==p[k];j++,k++);if (k==p.length()){return i;}i++;}return0;}int index1(string s,string p){int i=0,j=0;while (i<s.length() && j<p.length()) //j⼀旦超过模式长度，代表匹配成功，跳出循环{if (s[i]==p[j]){i++;j++;}else{i=i-j+1; //回溯j=0;}}if (j>=p.length()){return i-p.length(); //返回匹配成功的位置}elsereturn0;}int main(){string s,p;cin>>s>>p;cout<<"BF1算法匹配结果为:"<<index(s,p)<<endl;cout<<"BF2算法匹配结果为:"<<index1(s,p)<<endl;return0;}算法不考虑时间复杂度和空间复杂度，这是最简单也是我们很容易想到的⼀种算法思想。

bf算法最坏的空间复杂度最坏情况下，Brute-Force（BF）算法的空间复杂度是多少呢？在探讨这个问题之前，我们先来了解一下BF算法的基本原理和应用场景。

BF算法，也被称为暴力匹配算法或朴素匹配算法，是一种简单直接的模式匹配算法。

它的基本思想是，从文本串的第一个字符开始，与模式串的第一个字符进行比较，如果相等，则继续比较下一个字符；如果不相等，则将文本串的指针向后移动一位，再次与模式串的第一个字符进行比较。

如此循环下去，直到找到完全匹配或者文本串遍历结束。

BF算法的应用场景非常广泛，比如字符串匹配、模式识别、文本搜索等。

它的优点是简单易懂、实现简单，适用于小规模数据的匹配。

但是，正是由于其暴力的匹配方式，使得在某些情况下，其空间复杂度会达到最坏情况。

在BF算法中，空间复杂度主要来自于两个方面：文本串和模式串的存储。

文本串的存储。

在BF算法中，需要将待匹配的文本串存储在内存中，以便进行字符的比较。

假设文本串的长度为n个字符，那么需要占用n个存储单元的空间。

模式串的存储。

模式串是我们要匹配的目标，同样需要将其存储在内存中。

假设模式串的长度为m个字符，那么需要占用m个存储单元的空间。

BF算法的空间复杂度为O(n+m)。

当文本串和模式串长度较大时，其空间复杂度也会相应增加。

虽然BF算法的空间复杂度并不是最优的，但在某些场景下，它依然具有一定的优势。

比如在处理小规模数据时，BF算法的实现简单高效；在需要精确匹配的情况下，BF算法可以找到所有匹配的结果。

然而，当面对大规模数据时，BF算法的空间复杂度可能成为一个问题。

在这种情况下，我们可以考虑其他更高效的算法，比如KMP算法、Boyer-Moore算法等，它们可以在减少空间复杂度的同时，提高匹配效率。

总结起来，BF算法的最坏空间复杂度为O(n+m)，其中n为文本串的长度，m为模式串的长度。

虽然其空间复杂度可能不是最优的，但在某些场景下仍然具有一定的优势。

字符串模式匹配算法系列（⼀）：BF算法算法背景：BF（Brute Force）算法，是⼀种在字符串匹配的算法中，⽐较符合⼈类⾃然思维⽅式的⽅法，即对源字符串和⽬标字符串逐个字符地进⾏⽐较，直到在源字符串中找到完全与⽬标字符串匹配的⼦字符串，或者遍历到最后发现找不到能匹配的⼦字符串。

算法思路很简单，但也很暴⼒。

算法原理：假设源字符串为“⾮常地⾮常地⾮常地喜欢你”，我们想从中寻找⽬标字符串“⾮常地⾮常地喜欢”，则BF算法的过程可以表述如下：第1轮：将源字符串和⽬标字符串对齐，并下标0开始逐个向后⽐较每个字符。

结果发现双⽅的第1个字符都是“⾮”、第2个字符都是“常”、……，但到了第7个字符时发现不⼀致：源字符串为“⾮”、⽬标字符串为“喜”，因此这⼀轮匹配不成功。

第2轮：将⽬标字符串整体向后移动1个字符的位置（即将⽬标字符串的第1个字符与源字符串的第2个字符对齐），并开始逐个向后⽐较每个字符，结果发现两个字符串的第1个字符就不⼀致，因此这⼀轮匹配也不成功。

第3轮：类似地，将⽬标字符串整体向后移动1个字符的位置（即将⽬标字符串的第1个字符与源字符串的第3个字符对齐），并开始逐个向后⽐较，结果发现两个字符串的第1个字符就不⼀致，因此这⼀轮匹配也不成功。

第4轮：这⼀轮终于发现，⽬标字符串的每个字符都能和源字符串对应起来，匹配成功！因此算法结束并根据需要返回相应的信息（⽐如返回这⼀轮源字符串遍历起始点的位置下标3）算法实现：BF算法的python实现如下：1#!/usr/bin/env python2#-*- coding: utf-8 -*-3import sys4import pdb56 reload(sys)7 sys.setdefaultencoding('utf-8')8910class BruteForce(object):11"""BF算法12成员变量:13 str_s: 源字符串14 str_t: ⽬标字符串15"""16def__init__(self, str_s, str_t):17 self.str_s = str_s18 self.str_t = str_t1920def run(self):21"""完全匹配则返回源字符串匹配成功的起始点的下标，否则返回-122"""23 base = 0 # 记录源字符串与⽬标字符串对齐的基准点24 len_s = len(self.str_s)25 len_t = len(self.str_t)2627while base + len_t <= len_s:28 step = 029while step < len_t:30if str_t[step] == self.str_s[base + step]:31# 当前字符相同，则继续⽐较下⼀个字符32 step += 133continue34# 当前字符不相同，则结束次轮⽐较，更新base基准位置，启动下⼀轮⽐较35 base += 136break37# 完全匹配成功，算法结论，返回匹配成功的基准点位置下标38if step == len_t:39return base40# 遍历了所有情况，最终匹配失败，返回-141return -1424344if__name__ == '__main__':45 str_s = u"⾮常地⾮常地⾮常地喜欢你"46 str_t = u"⾮常地⾮常地喜欢"47 model = BruteForce(str_s, str_t)48print model.run()复杂度分析：时间复杂度：假设源字符串长度为m，⽬标字符串长度为n，则：最好情况下是第⼀轮就成功匹配，则时间复杂度为O(n)；最坏情况下是遍历到最后才成功匹配，或者遍历到最后发现匹配不成功，则时间复杂度为O(n*(m-n+1))，⼀般实际使⽤时m >> n，所以可以认为趋近于O(m*n)；空间复杂度：由于不需要额外的存储空间，所以空间复杂度为O(1)算法评估：整个算法其实就循环执⾏如下两个步骤：⼀、从每⼀轮的基准点开始⽐较两个字符串；⼆、如发现不能完全匹配⽬标字符串，将⽬标字符串向后挪动⼀个字符的位置（即更新基准点）；如果想优化算法性能，那就简单分析⼀下：步骤⼀基本没有优化的空间：两个字符串⽐较就是需要从前向后逐个字符看是否匹配；步骤⼆可能有优化的空间：每轮发现不匹配时，⽬标字符串只能向后挪动⼀个字符的距离，所以会想到能否多往后挪动⼏个字符的距离？这样不就减少了步骤⼀⽐较的轮次数，从⽽加快速度了吗？这基本就是KMP算法的思路，下⼀篇会详细介绍。