大話資料結構十：字元串的模式比對（BF算法）

1. 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 )。