Analysis

Remember that |P| = m, |T| = n.

Inner loop will take m steps to confirm the pattern matches

Outer loop will take n-m+1 steps

Therefore, worst case is $\Theta((n-m+1)m)$


next up previous
Next: More Analysis Up: NAIVE PATTERN MATCHER Previous: Algorithm