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 }