## Brute Force

Brute force pattern matching involves executing a search at every point in the target string, and attempting to look over the length of the pattern.

### Worst Case

T = aaaaaa....aaaah P = aaaaaah

### Complexity

O(nm), every item in T must be matched to every item in P.

## Boyer-Moore

Booyer Moore looks to improve basic Brute Force Matching.

It works by lining T and P up, and checking the last character in P against T[len(P)-1]. If this character matches, the second last character is checked, and so on. Upon failure, rather than just shifting the Pattern across by one, it can be observed that if c is the character in T that we are trying to match, we can re-align P such that c lines up with the last occurrence of c in P.

### Worst Case

T = aaaaaaaaaaaaa P = baaaaa

### Complexity

O(nm + s), whilst this algorithm appears to be equal in complexity to the Brute force method, it is actually significantly faster for English Text (Around 1/4 of the operations required).

## KMP (Knuth-Morris-Pratt)

KMP basically calculates how far the pattern can be shifted if it fails after a particular point.

T abaab|x P abaab|a P ab|aaba

If we fail after successfully matching abaab, then we can infer that we can shift the pattern 3 spaces, and know that the first ab will already match.

### Complexity

O(m+n), Much better than Boyer-Moore!