    Next: Research with an automaton Up: ESMAJ Prev: Introduction

# Brute Force algorithm

Main features
• no preprocessing phase;
• constant extra space needed;
• always shifts the window by exactly 1 position to the right;
• comparisons can be done in any order;
• searching phase in O(mn) time complexity;
• 2n expected text characters comparisons.
Description

The brute force algorithm consists in checking, at all positions in the text between 0 and n-m, whether an occurrence of the pattern starts there or not. Then, after each attempt, it shifts the pattern by exactly one position to the right.

The brute force algorithm requires no preprocessing phase, and a constant extra space in addition to the pattern and the text. During the searching phase the text character comparisons can be done in any order. The time complexity of this searching phase is O(mn) (when searching for am-1b in an for instance). The expected number of text character comparisons is 2n.

The C code
```void BF(char *x, int m, char *y, int n) {
int i, j;

/* Searching */
for (j = 0; j <= n - m; ++j) {
for (i = 0; i < m && x[i] == y[i + j]; ++i);
if (i >= m)
OUTPUT(j);
}
}

```

This algorithm can be rewriting to give a more efficient algorithm in practice as follows:

```#define EOS '\0'

void BF(char *x, int m, char *y, int n) {
char *yb;
/* Searching */
for (yb = y; *y != EOS; ++y)
if (memcmp(x, y, m) == 0)
OUTPUT(y - yb);
}

```

However code optimization is beyond the scope of this book.

The example

Searching phase    Next: Research with an automaton Up: ESMAJ Prev: Introduction

e-mails: {Christian.Charras, Thierry.Lecroq}@laposte.net
Tue Jan 14 15:03:31 MET 1997