本文主要介绍字符串匹配的暴力搜索算法
主要特征
1、没有预处理阶段
2、需要常量额外空间
3、通常需要模式串窗口向右移动一个位置
4、可以按照任意顺序进行比较
5、搜索的时间复杂度为O(mn)
6、文本字符期望比较次数:2n
算法描述
暴力搜索算法由文本串中从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 |
No comments yet.
Comments