字符串匹配--暴力搜索算法，字符串--暴力算法
主要特征
1、沒有預處理階段
2、需要常量額外空間
3、通常需要模式串窗口向右移動一個位置
4、可以按照任意順序進行比較
5、搜索的時間復雜度為O(mn)
6、文本字符期望比較次數:2n
本文地址：http://www.cnblogs.com/archimedes/p/brute-force-algorithm.html，轉載請注明源地址。
算法描述
暴力搜索算法由文本串中從0到n-m所有位置的比較組成，無論是否從模式串的起始位置開始，每次匹配過後，模式串向右移動一位。暴力搜索算法沒有預處理階段，文本串和模式串需要常量額外空間，在搜索階段的文本串的字符可以按照任意順序進行比較，匹配的時間復雜度為O(mn)，
C代碼實現
int BF(char *x, int m, char *y, int n) {
int i, j;
/* 搜索*/
for (j = 0; j <= n - m; ++j) {
for (i = 0; i < m && x[i] == y[i + j]; ++i);
if (i >= m)
return j;
}
}
上面的算法可以改寫為下面更加高效的算法：
#define EOS '\0'
int BF(char *x, int m, char *y, int n) {
char *yb;
/* 匹配*/
for (yb = y; *y != EOS; ++y)
if (memcmp(x, y, m) == 0)
return y - yb;
}
舉例
第1次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
2
3
4
G
C
A
G
A
G
A
G
第2次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第3次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第4次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第5次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第6次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
2
3
4
5
6
7
8
G
C
A
G
A
G
A
G
第7次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第8次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第9次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
2
G
C
A
G
A
G
A
G
第10次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第11次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
2
G
C
A
G
A
G
A
G
第12次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第13次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
2
G
C
A
G
A
G
A
G
第14次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第15次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第16次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
第17次嘗試
G
C
A
T
C
G
C
A
G
A
G
A
G
T
A
T
A
C
A
G
T
A
C
G
1
G
C
A
G
A
G
A
G
想找一個解決兩個字符串匹配程度的算法
假設string1="abcde",string2="bcd",則分析邏輯如下：
1. 如果string2長於string1，則不匹配
2. 在string1中順序查匹配string2中第一個字符的字符，
查到後，如果string1余下的字符串長度小於string2的長度，則不匹配
3. 在上述條件滿足時，將string1的下一個字符和string2中的第二個字符匹配，以此類推，一旦有一個不匹配，則不匹配。回到第2步，查找下一個和string2首字符一致的字符。
4. 如果string2中的字符全都匹配上，則說明string2中string1中識別出來了。
字符串匹配算法
樓主，你指的“多重算法”是什麼意思？ 多重匹配但只掃描一次？
