BF算法(Brute Force)
更新时间 2021-07-21 18:27:18    浏览 0   

TIP

本文主要是介绍 BF算法(Brute Force) 。

# 1、BF算法的基本思想

BF(Brute Force)算法是模式匹配中最简单、最直观的算法。该算法最基本的思想是从主串的第 start 个字符起和模式P(要检索的子串)的第1个字符比较,如果相等,则逐个比较后续字符;比较过程中一旦发现不相等的情况,则回溯到主串的第 start+1 个字符位置,重新和模式P的字符进行比较。

wxmp

# 2、算法代码

 1 package algorithm;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * 字符串匹配算法:BF
 7  */
 8 public class BF {
 9     // 主串
10     private String s1;
11     // 目标串
12     private String s2;
13 
14     /**
15      * 控制台输入主串、目标串
16      * 使用{@link Scanner#nextLine}能接收当前行(非结尾的)的其余部分,包括空格。
17      * 当然使用Scanner是其中的一种方法。
18      */
19     public void read() {
20         // 输入主串
21         System.out.println("请输入主串: ");
22         Scanner scan = new Scanner(System.in);
23         // 输入要匹配得字符
24         System.out.println("请输入目标串: ");
25         Scanner aim = new Scanner(System.in);
26         if (scan.hasNext()) {
27             s1 = scan.nextLine();
28             System.out.println("输入的主串为:" + s1);
29         }
30         if (aim.hasNext()) {
31             s2 = aim.nextLine();
32             System.out.println("输入的目标串为:" + s2);
33         }
34 
35         if (s1.length() < s2.length()) {
36             System.out.println("主串长度必须大于目标串,请重新输入!");
37             read();
38         }
39 
40         // 关闭
41         scan.close();
42         aim.close();
43     }
44 
45     /**
46      * 字符串匹配算法BF,算法平均时间复杂度为O((n-m)m),n为主串长度,m为目标串长度。
47      *
48      * @param start 从主串的start位置开始匹配
49      * @return true 匹配成功,反之失败
50      */
51     public boolean bf(int start) {
52         read(); // 输入主串,目标串参数
53         int i, j;
54         for (i = start; i < s1.length() - s2.length(); ) {
55             for (j = 0; j < s2.length(); j++) {
56                 if (s1.charAt(i) != s2.charAt(j)) {
57                     i++;
58                     break;  // 从主串下一个字符重新开始找起,就像回溯
59                 } else {
60                     i++;    // 匹配成功,开始对比两个串的下一个字符
61                 }
62                 // 目标串匹配完后,返回会匹配成功的结果
63                 if (j == s2.length() - 1) {
64                     return true;
65                 }
66             }
67         }
68         return false;
69     }
70 
71 }

# 3、BF算法平均时间复杂度:

O((n-m)m),n为主串长度,m为目标串长度。BF算法可能会频繁地回溯,工作效率不会很高。

# 参考文章

  • https://www.cnblogs.com/gaochundong/p/string_matching.html
  • https://www.cnblogs.com/magic-sea/tag/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95/
更新时间: 2021-07-21 18:27:18
  0
手机看
公众号
讨论
左栏
全屏
上一篇
下一篇
扫一扫 手机阅读
可分享给好友和朋友圈