一、BF算法的基本思想
BF（Brute Force）算法是模式比對中最簡單、最直覺的算法。該算法最基本的思想是從主串的第 start 個字元起和模式P（要檢索的子串）的第1個字元比較，如果相等，則逐個比較後續字元；比較過程中一旦發現不相等的情況，則回溯到主串的第 start+1 個字元位置，重新和模式P的字元進行比較。
二、算法代碼
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 } BF算法平均時間複雜度為O((n-m)m)，n為主串長度，m為目标串長度。BF算法可能會頻繁地回溯，工作效率不會很高。