精华内容
下载资源
问答
  •  BF算法是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较...
  • 记录一下串里面的模式匹配模式匹配,顾名思义就是给定一个被匹配字符串,然后用一个字符串模式(模型)去匹配上面说的字符串,看后者是否在前者里面出现。常用的有2种算法可以实现,下面我们来具体探讨下
  • 一、先要掌握的概念:字符串:是由零个或多个字符组成的有限序列字串:串中任意个 连续的 字符组成的子序列子串在主串中的位置表示:以子串的第一个字符在主串的位置来表示模式匹配:也就是求子串在主串中的位置模式...

    一、先要掌握的概念:

    字符串:是由零个或多个字符组成的有限序列

    字串:串中任意个 连续的 字符组成的子序列

    子串在主串中的位置表示:以子串的第一个字符在主串的位置来表示

    模式匹配:也就是求子串在主串中的位置

    模式串:子串

    二、算法的大概思想:

    围绕暴力和回溯的思想,也就是从主串的第一个字符开始一个个往下走+1

    假设现有主串S (String) 和子串T  (String),求字串T在主串S中的位置;建立两个指针i和j分别指向主串和子串的第一个字符,

    然后利用i和j所指的字符开始逐个字符逐个字符的作比较,当S[i]==T[j]是,则当前的字符相同继续往下走,就是i++,j++;

    当S[i]!=T[j]是,则匹配失败,我们需要回溯:就是i知道比较之前的位置的下一个,j则从首字符开始,就是i= i-j+1;j=0;

    当j>=T.length是匹配成功

    eg:S = "ABABC"

           t = "BC"

    第一次:i= 0,j = 0  ,S[i]!=T[j],回溯 i = i-j+1 = 1,j = 0;

    第二次:i=1 ,j = 0,S[i] = T[j],i++,j++ ,i = 2,j = 1;S[i]!=T[j],回溯:i=i-j+1 = 2,j = 0;

    第三次:i= 2,j = 0,S[i]!=T[j],回溯:i = i-j+1 = 3,j = 0;

    第四次:i= 3,就= 0,S[i] = T[j],i++,j++,i = 4,j = 1,S[i]=T[j] ,j>=T.length(),所以匹配成功


    三、代码.java

    import java.util.*;
    public class MoshiMatch {
     public static void main(String[] args) throws Exception {
      // TODO Auto-generated method stub
      Scanner in = new Scanner(System.in);
      String S = in.next();
      String T = in.next();
      System.out.println(violentMatching(S, T));
     }
     
     public static int violentMatching(String s,String t) {
      int sl = s.length();
      int tl = t.length();
      
      int i = 0;
      int j = 0;
     
      while(i<sl&&j<tl) {
       if(s.charAt(i)==t.charAt(j)) {
        i++;
        j++;
       }
       else {
        i = i-j+1;
        j = 0;
       }
      }
      
      if(j>=t.length()) return i-j;
      else return -1;
      }
    }


    展开全文
  • \quad \quad设 S 和 T 是给定的两个串,在主串 S 中找到模式串 T 的过程称为字符串匹配,如果在主串 S 中找到模式串 T ,则称匹配成功,函数返回 T 在 S 中首次出现的位置,否则匹配不成功,返回 -1。 例: 在上图...

    引言

    字符串模式匹配:

    \quad \quad 设 S 和 T 是给定的两个串,在主串 S 中找到模式串 T 的过程称为字符串匹配,如果在主串 S 中找到模式串 T ,则称匹配成功,函数返回 T 在 S 中首次出现的位置,否则匹配不成功,返回 -1。

    例:
    在这里插入图片描述
    在上图中,我们试图找到模式串 T = baab,在主串 S = abcabaabcabac 中第一次出现的位置,即为红色阴影部分, T 第一次在 S 中出现的位置下标为 4 ( 字符串的首位下标是 0 ),所以返回 4。如果模式串 T 没有在主串 S 中出现,则返回 -1。

    1、基本思想

    BF算法,即暴力(Brute Force算法),又称朴素算法

    基本思想:

    \quad \quad 从主串S的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较后者的后续字符;否则,从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,直到T中的字符全部比较完毕,则说明本趟匹配成功;或S中字符全部比较晚,则说明匹配失败。

    2、伪代码

    1、在串S和串T中初始下标i=0和j=0
    2、循环直到S或T的所有字符均未比较完:

    • 2.1 如果S[i]==T[j],继续比较S和T的下一个字符
    • 2.2 否则,将i回溯到i-j+1,j回溯到0,重新比较

    3、如果T中所有字符均比较完,则匹配成功,返回匹配的起始下标;否则匹配失败,返回-1。

    3、代码实现

    def BF(s,t):
        i=0
        j=0
        while i<len(s) and j<len(t):
            if s[i]==t[j]:
                i+=1
                j+=1
            else:
                i=i-j+1
                j=0
        if j>=len(t):
            return i-len(t)
        else:
            return -1
    if __name__=="__main__":
        s="abcabaabcabac"
        t="baab"
        b=BF(s,t)
        print(b)
    
    • 时间复杂度: O ( m ∗ n ) O(m*n) O(mn),其中m,n分别为主串、模式串的长度
    • 空间复杂度: O ( 1 ) O(1) O(1)
    展开全文
  • 模式匹配含义:给定两个字符串,在主串s中查找子串T的过程就称为字符串模式匹配BF算法:基本思想就是暴力匹配,将子串的第一个字符与主串的第一个字符进行比较,若相等,则比较第二个字符。若不相等,则与主串...

    模式匹配含义:给定两个字符串,在主串s中查找子串T的过程就称为字符串的模式匹配。
    BF算法:基本思想就是暴力匹配,将子串的第一个字符与主串的第一个字符进行比较,若相等,则比较第二个字符。若不相等,则与主串的第二个字符进行比较,以此类推,直到匹配到为止。
    代码如下

      //返回模式串t在主串中从start开始的第一次匹配位数
        public int indexOf(SeqString t,int start){
            if (this!=null && t!=null && t.length()>0 && this.length()>t.length()){
                int slen,tlen,i=start,j=0;
                slen=this.length();
                tlen=t.length();
                while (i<slen && j<tlen){
                    if (this.charAt(i)==t.charAt(j)){
                        i++;
                        j++;
                    }
                    else{
                        //继续比较下一个字串
                        i=i-j+1;
                        j=0;
                    }
                }
                if (j>t.length()){
                    //匹配成功,返回子串序号
                    return i-tlen;
                }
                else{
                    return -1;
                }
            }
            return -1;
        }
    

    KMP算法是一种改进的字符串匹配算法,主要实现方式是主串的x指针不回溯,修改y指针的指向,使其移动到有效的位置,从而大大提高了字符串匹配效率。

    next指针的作用:当x与y指针指向的字符不同时,让y指针指向next[y]对应的位置即可。

    next数组保存的就是已匹配过子串前缀的“最长可匹配前缀子串”和“最长可匹配后缀子串”的最长共有元素的长度。

    获取next数组代码

     public static int[] getNext(String str){
            int[] next=new int[str.length()];
            next[0]=-1;
            //y为索引,len为最长共有元素的长度
            int y=0,len=-1;
            //定义一个循环,用来计算next数组
            while (y<str.length()-1){
                //处理len何y指向模式串中字符相等的情况
                if (len==-1 || str.charAt(len)==str.charAt(y)){
                    y++;
                   len++;
                   next[y]=len;
                }
                //处理len何y指向模式串中字符不相等的情况
                else{
                    len=next[len];
                }
            }
            return next;
        }
    
    

    KMP算法代码

    public static int KmpSearch(String str1,String str2){
            int[] next=getNext(str2);
            int x=0,y=0;
            while (x<str1.length()&& y<str2.length()){
                if (y==-1 || str1.charAt(x)==str2.charAt(y)){
                    x++;
                    y++;
                }
                else{
                    y=next[y];
                }
            }
            if (y==str2.length()){
                return x-y;
            }
            return -1;
        }
    

    获取next数组优化算法代码

      public static int[] getNext(String str){
            int[] next=new int[str.length()];
            next[0]=-1;
            //y为索引,len为最长共有元素的长度
            int y=0,len=-1;
            //定义一个循环,用来计算next数组
            while (y<str.length()-1){
                //处理len何y指向模式串中字符相等的情况
                if (len==-1 || str.charAt(len)==str.charAt(y)){
    //                y++;
    //                len++;
                    //如果len和y指向的字符相等  KMP算法优化
                    if(str.charAt(++len)==str.charAt(++y)){
                        next[y]=next[len];
                    }
                    else{
                        next[y]=len;
                    }
                    next[y]=len;
                }
                //处理len何y指向模式串中字符不相等的情况
                else{
                    len=next[len];
                }
            }
            return next;
        }
    

    完整代码如下

     //实现KMP算法
        public static int KmpSearch(String str1,String str2){
            int[] next=getNext(str2);
            int x=0,y=0;
            while (x<str1.length()&& y<str2.length()){
                if (y==-1 || str1.charAt(x)==str2.charAt(y)){
                    x++;
                    y++;
                }
                else{
                    y=next[y];
                }
            }
            if (y==str2.length()){
                return x-y;
            }
            return -1;
        }
        //计算next数组
        public static int[] getNext(String str){
            int[] next=new int[str.length()];
            next[0]=-1;
            //y为索引,len为最长共有元素的长度
            int y=0,len=-1;
            //定义一个循环,用来计算next数组
            while (y<str.length()-1){
                //处理len何y指向模式串中字符相等的情况
                if (len==-1 || str.charAt(len)==str.charAt(y)){
    //                y++;
    //                len++;
                    //如果len和y指向的字符相等  KMP算法优化
                    if(str.charAt(++len)==str.charAt(++y)){
                        next[y]=next[len];
                    }
                    else{
                        next[y]=len;
                    }
                    next[y]=len;
                }
                //处理len何y指向模式串中字符不相等的情况
                else{
                    len=next[len];
                }
            }
            return next;
        }
    
    
    展开全文
  • 算法代码】 #include <bits/stdc++.h> using namespace std; int BF(string S,string T) { int i=0; int j=0; while(i<S.length() && j<T.length()) { if(S[i]==T[j]) { i++; j...

    【算法代码】

    #include <bits/stdc++.h>
    using namespace std;
    
    int BF(string S,string T) {
    	int lens=S.length(); //First of all, you must calculate the length of the string.
    	int lent=T.length();
    	int i=0;
    	int j=0;
    	while(i<lens && j<lent) {
    		if(S[i]==T[j]) {
    			i++;
    			j++;
    		} 
    		else {
    			i=i-j+1;
    			j=0;
    		}
    	}
    	
    	if(j==lent)
    		return i-j+1;
    	else
    		return -1;
    }
    
    int main() {
    	string S,T;
    	getline(cin,S);
    	getline(cin,T);
    	
    	cout<<BF(S,T)<<endl;
    	
    	return 0;
    }
    
    /*
    input:
    abefdeffabc
    effa
    
    output:
    6
    */

     

    展开全文
  • *串的模式匹配-BF算法 *找到相同的字符串输出在原字符串中的位置 代表匹配字符串在原字符串中的位置 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define STRSIZE 255//字符串的...
  • @Adrian ...普通模式匹配算法,其实现过程没有任何技巧,就是简单粗暴地拿一个同另一个中的字符一一比对,得到最终结果。 例如,使用普通模式匹配算法判断 A(“abcac”)是否为 B(“aba...
  • 经典算法-BF算法(字符串匹配

    千次阅读 2020-10-26 22:50:50
    字符串匹配算法也是很经典的一个算法,在面试的时候常常会遇到,而BF算法字符串模式匹配中的一个简单的算法 1,什么是BF算法 BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,思想简单,代码结构也简单...
  • 字符串模式匹配--BF算法&KMP算法

    千次阅读 多人点赞 2018-04-05 13:58:59
    BF算法是基于主指针回溯,重新与子串进行逐字符进行比较,主为S什么要进行回溯呢,原因在于模式P中存在相同的字符或者说由字符)存在重复(模式的部分匹配性质),设想如果模式P中字符各不相同,主就S的...
  • 模式匹配算法,通俗地理解,是一种用来判断两个之间是否具有"主与子串"关系的算法。 主与子串:如果 A(如 "shujujiegou")中包含有 B(如 "ju"),则称 A 为主 B 为子。主与子串之间的...
  • 依次类推,直至模式T中的每个字符依次和主S中的一个连续的字符序列相等,则称匹配成功,函数值为和模式T中的每个字符依次和主S中的序号,否则称匹配不成功,函数值为0,分别利用计数指针i和j指示主S和模式串T...
  • 字符串模式匹配BF算法

    千次阅读 2017-03-17 15:10:15
    暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一...蛮力搜索,比较简单的一种字符串匹配算法,在处理简单的数据时候就可以用这种算法,完全匹配,就是速度慢啊。基
  • 著名的模式匹配算法有BF算法和KMP算法,本文章主要着重讲KMP算法及其拓展。 【BF算法】 BF(Brute-Force)算法,是最简单直观的模式匹配算法。 看下图,上边的是主a,下边的是模式串b。分别用i,j做各自的指针...
  • #include<stdio.h> #include<...int BF(char* str1, char* str2, int length1, int length2, int pos); int main() { char* a = "abcdffllkh"; char* b = "fl"; int n = 0, m = 0; int k = ...
  • 模式匹配BF算法C/C++代码实现

    千次阅读 2020-06-05 11:25:13
    串: 串是一种内容受限的线性表。 与线性表基本操作不同的是...( 为了方便说明问题,算法描述当中所用到的顺序存储的字符串都是从下标为1的数组分量开始存储的, 下标为0的分量闲置不用) #include<stdio.h> #
  • 字符串模式匹配算法

    2021-05-21 08:21:37
    《数据结构(C语言版)》之“模式匹配算法模式匹配算法 >>>1.定义的顺序存储结构。 >>>2.编写函数实现# include # include # include # define OK 1 # define ERROR 0 typedef int ...
  • #include #include #define ERROR_LEN -2 //长度错误 #define NO_MATCH -1 //无匹配 int fun(char s[],char t[],int start){ //在t[]中查找s[] int i,j; int m,n; m=strlen(s);
  • 2.掌握字符串模式匹配算法BF算法或KMP算法的实现。 实验内容 问题描述 医学研究者最近发现了某些新病毒,通过对这些病毒的分析,得知它们的DNA序列都是环状的。现在研究者已收集了大量的病毒DNA和人的DNA数据,想快速...
  • 大连理工大学数据结构上机题字符串朴素模式匹配算法字符串朴素模式匹配算法字符串朴素模式匹配算法字符串朴素模式匹配算法
  • 《C语言》字符串匹配BF算法+KMP算法)

    千次阅读 多人点赞 2020-05-02 16:07:17
    字符串匹配 【问题描述】 对于字符串S和T,若T是S子串,返回T在S中的位置(T的首字符在S中对应的下标),否则返回-1. 【问题求解】 采用直接穷举法求解,称为BF算法。该算法从S的每一个字符开始查找,看T是否会出现...
  • 字符串匹配BF算法

    2017-04-11 15:02:23
    已知两个字符串,一个主串S,一个子串T,求子串在主串中是否出现。如果出现,输出子串在主串中的位置。 利用暴力求解算法,每次比较主串和子串中的一个字符是否相等,如果相等,两个串的下标均后移。如果不相等,...
  • 字符串模式匹配BF算法

    千次阅读 2013-12-15 22:30:13
    #include #include int BF_StrFind(char SrcStr[], char DstStr[]) { int SrcLen = 0; int DstLen = 0; int i = 0;... /*记录从源字符串中比较的位置*/ /*check paramter*/ if ((NU
  • C语言版本的字符串模式匹配,主要适用于学数据结构的孩纸,数据结构实验报告
  • KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数: ...
  • 本文详细介绍两种最常见的字符串模式匹配算法:朴素模式匹配KMP模式匹配字符串模式匹配,也称子串的定位操作,通俗的说就是在一个主串中判断是否存在给定的子串(又称模式串),若存在,则返回匹配成功的索引。...
  • 算法1:朴素模式匹配算法/简单匹配算法(Brute-Force算法,简称BF算法) 从目标主s=“s1s2…sn”s=“s_1s_2…s_n”s=“s1​s2​…sn​”的第一个字符开始和模式串p=“p1p2…pm”p=“p_1p_2…p_m”p=“p1​p2...
  • 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法(Next[ ]) 4.KMP改进算法(NextVal...
  • 这篇文章主要介绍了数据结构中的字符串以及有关字符串的很重要的算法——模式匹配算法,重点介绍了KMP算法的实现原理。
  • 1. 简单的模式匹配算法——BF模式匹配 模式匹配,是求模式串在主中的位置。时间复杂度 O(n*m). 下面来看一下代码 int Index(SString S, SString T, int pos){ int i = pos; int j = 1; while(i <= S....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,154
精华内容 4,061
关键字:

字符串模式匹配bf算法