9. Week 08: Searching in Strings

• 9.1. Substring Search
  • 9.1.1. Testing a search procedure
  • 9.1.2. A very naive search
  • 9.1.3. A slightly better naive search
  • 9.1.4. A recursive version of the naive search
  • 9.1.5. Testing naive search
• 9.2. Rabin-Karp Search
  • 9.2.1. Recursive version of Rabin-Karp search
  • 9.2.2. Comparing performance of search procedures
• 9.3. Knuth–Morris–Pratt Algorithm
  • 9.3.1. Revisiting the naive algorithm
  • 9.3.2. Returning the Interrupt Index
  • 9.3.3. Relating Matched Text and the pattern
  • 9.3.4. Fast-Forwarding Search using Interrupt Index
  • 9.3.5. Extracting the Interrupt Index
  • 9.3.6. Exploiting the Prefix Equality
  • 9.3.7. Tabulating the interrupt indices
  • 9.3.8. Boot-strapping the table
  • 9.3.9. Comparing performance, again
• 9.4. Exercises
  • 9.4.1. Exercise 1
  • 9.4.2. Exercise 2
  • 9.4.3. Exercise 3