Substring Search

• Sedgewick - Suffix Arrays - Coursera (video)
• Sedgewick - Substring Search - Coursera
  • 1. Introduction to Substring Search (video)
  • 2. Brute-Force Substring Search (video)
  • 3. Knuth-Morris Pratt (video)
  • 4. Boyer-Moore (video)
  • 5. Rabin-Karp (video)
• Search pattern in text - Coursera (video)

More String Matching

• Rabin-Karp:
  • Rabin Karps Algorithm - Coursera (video)
  • Precomputing - Coursera (video)
  • Optimization: Implementation and Analysis - Coursera (video)
  • Table Doubling, Karp-Rabin - MIT 6.006 (video)
  • Rolling Hashes, Amortized Analysis - MIT 6.006 (video)
• Knuth-Morris-Pratt (KMP):
  • Knuth-Morris-Pratt (KMP) String Matching Algorithm - Youtube (video)
• Boyer–Moore:
  • Boyer-Moore String Search Algorithm - Wikipedia (article)
  • Advanced String Searching Boyer-Moore-Horspool Algorithms - Youtube (video)
• Course: Algorithms on Strings - Coursera (web)
  • starts off great, but by the time it gets past KMP it gets more complicated than it needs to be
  • nice explanation of tries
  • can be skipped