9. YSC2229 Lecture Notes, Week 09

• 9.1. Substring Search
  • 9.1.1. Testing a search procedure
  • 9.1.2. A naive search
  • 9.1.3. A recursive version of the naive search
  • 9.1.4. Generating strings for testing search function
  • 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. Mandatory exercises
  • 9.4.2. Recommended exercises
  • 9.4.3. Exercise 1
  • 9.4.4. Exercise 2
  • 9.4.5. Exercise 3
  • 9.4.6. Exercise 4
  • 9.4.7. Exercise 5

Supplementary materials

• Naive String Search
• Rabin-Karp algorithm
• Knuth-Morris-Pratt algorithm
• Comparison of performance
• Automated Tests