# 工学1号馆

home

## Brute Force algorithm

Wu Yudong    September 26, 2015     Algorithm   554

### 主要特征

1、没有预处理阶段

2、需要常量额外空间

3、通常需要模式串窗口向右移动一个位置

4、可以按照任意顺序进行比较

5、搜索的时间复杂度为O(mn)

6、文本字符期望比较次数:2n

### 算法描述

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;
}

 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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