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

大话数据结构十：字符串的模式匹配（BF算法）2014-12-301. BF算法简介：

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

2. BF算法思想:

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