字符串与模式匹配算法（一）：BF算法

一、BF算法的基本思想

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

二、算法代码

package algorithm;

import java.util.Scanner;

/**
 * 字符串匹配算法：BF
 */
public class BF {
    // 主串
    private String s1;
    // 目标串
    private String s2;

    /**
     * 控制台输入主串、目标串
     * 使用{@link Scanner#nextLine}能接收当前行(非结尾的)的其余部分，包括空格。
     * 当然使用Scanner是其中的一种方法。
     */
    public void read() {
        // 输入主串
        System.out.println("请输入主串: ");
        Scanner scan = new Scanner(System.in);
        // 输入要匹配得字符
        System.out.println("请输入目标串: ");
        Scanner aim = new Scanner(System.in);
        if (scan.hasNext()) {
            s1 = scan.nextLine();
            System.out.println("输入的主串为：" + s1);
        }
        if (aim.hasNext()) {
            s2 = aim.nextLine();
            System.out.println("输入的目标串为：" + s2);
        }

        if (s1.length() < s2.length()) {
            System.out.println("主串长度必须大于目标串，请重新输入！");
            read();
        }

        // 关闭
        scan.close();
        aim.close();
    }

    /**
     * 字符串匹配算法BF，算法平均时间复杂度为O((n-m)m)，n为主串长度，m为目标串长度。
     *
     * @param start 从主串的start位置开始匹配
     * @return true 匹配成功，反之失败
     */
    public boolean bf(int start) {
        read(); // 输入主串，目标串参数
        int i, j;
        for (i = start; i < s1.length() - s2.length(); ) {
            for (j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) != s2.charAt(j)) {
                    i++;
                    break;  // 从主串下一个字符重新开始找起，就像回溯
                } else {
                    i++;    // 匹配成功，开始对比两个串的下一个字符
                }
                // 目标串匹配完后，返回会匹配成功的结果
                if (j == s2.length() - 1) {
                    return true;
                }
            }
        }
        return false;
    }

}

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