String Matching

• $strcmp$ takes $\Theta (m)$!!

• Basically two categories? Pre-process $P$ and Pre-process $T$.
  • P is the pattern
    • Karp-Rabin Algorithm
    • Boyer-Moore Algorithm
    • String Matching with Finite Automata - also not going to be tested on this
    • Knuth-Morris-Pratt Algorithm
  • T is extra processing on the text
    • We are not going to be tested on those