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!