大话数据结构十：字符串的模式匹配（BF算法）

1. BF算法简介：

BF(Brute Force)算法是普通的模式匹配算法，又称为朴素匹配算法或蛮力算法，该算法最大缺点就是字符匹配失败指针就要回溯，所以性能很低。

2. BF算法思想:

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。

3. Java实现:

// 朴素匹配算法
public class BruteForce {
    /**
     * @param mainStr 主串
     * @param subStr 子串
     * @return 字符串匹配成功起始位置
     */
    public static int getMatchIndex(String mainStr, String subStr) {
        int i = 0, j = 0;
        while (i < mainStr.length()) {
            if (mainStr.charAt(i) == subStr.charAt(j)) { // 两字母相等则继续
                i++;
                j++;
            } else { // 两字母不等则角标后退重新开始匹配
                i = i - j + 1; // i 回退到上次匹配首位的下一位
                j = 0; // j 回退到子串的首位
            }
            if (j == subStr.length())
                return i - j;
        }
        return -1;
    }  

    public static void main(String[] args) {
        System.out.println("匹配成功的位置为: " + getMatchIndex("god is a girl", "girl"));
    }  

}

注: 其实Java API中已经实现了字符串匹配这一算法,如: "abc".indexOf("bc") 将会返回1。这里仅仅是模拟该算法，仅供参考。

4. BF算法时间复杂度:

该算法最坏情况下要进行 M * ( N - M + 1) 次比较，时间复杂度为 O ( M * N )。

作者：csdn博客 zdp072

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， 数据结构算法
， 字符串
， 算法 数据结构 图论
， 复杂度
， 字符
， 蛮力算法
， 模式
， 模式匹配算法
， substr
， 字符串匹配算法
， BF算法
， 蛮力匹配
朴素字符匹配
，以便于您获取更多的相关知识。