22
Pattern Matching: Brute-force, Analysis
Brute-force pattern matching runs in O(n·m)
Examples of worst case (forward checking):
T
=
aaa…ah
P
=
aaah
may occur in DNA sequences
unlikely in English text