I failed to create something new, but I'll share my thought process, and how it almost led me to reinventing a well-known solution.

Table of contents

• Prelude.
• The naive implementation.
• The thought process.
• The algorithm.
• The Karp, and the Rabin.
• Closing thoughts.
• Homework.
• Extras:
  • Can the algorithm overflow?
  • XOR variation.
  • Inputs that trigger the worst-case performance.
  • Fun results for tiny inputs.
  • Tiny puzzle.
  • Code for the needle crate.
  • Comment section.

Prelude

needle = 'needle'
haystack = 'do I have a needle? Yes I do'

assert(needle in haystack)