8. Chapter 08: Searching in Strings

• 8.1. Substring Search
  • 8.1.1. Testing a search procedure
  • 8.1.2. A very naive search
  • 8.1.3. A slightly better naive search
  • 8.1.4. A recursive version of the naive search
  • 8.1.5. Testing naive search
• 8.2. Rabin-Karp Search
  • 8.2.1. Recursive version of Rabin-Karp search
  • 8.2.2. Comparing performance of search procedures
• 8.3. Knuth–Morris–Pratt Algorithm
  • 8.3.1. Revisiting the naive algorithm
  • 8.3.2. Returning the Interrupt Index
  • 8.3.3. Relating Matched Text and the pattern
  • 8.3.4. Fast-Forwarding Search using Interrupt Index
  • 8.3.5. Extracting the Interrupt Index
  • 8.3.6. Exploiting the Prefix Equality
  • 8.3.7. Tabulating the interrupt indices
  • 8.3.8. Boot-strapping the table
  • 8.3.9. Comparing performance, again
• 8.4. Exercises
  • 8.4.1. Exercise 1
  • 8.4.2. Exercise 2
  • 8.4.3. Exercise 3