about summary refs log tree commit diff
path: root/lisp/f
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-11-16T17·14+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-11-16T17·14+0000
commit6989c3a91a99d18fbe527fd453e2f1f9a5a1c1af (patch)
treea16408275f3b5f884f099f6c880f58835779ece4 /lisp/f
parenta2fa88f5611f878c6937abaab4f6858a203c37b6 (diff)
Implement the Rabin Karp string matching algorithm
This algorithm is pretty interesting because it runs in linear time with respect
to the length of the `corpus` string. It does this by using a sliding window
hash. This hash -- because it's a sliding window -- runs in constant time for
each iteration; we're only adding and subtracting one character each time and
not re-hashing the whole "window".

When our hashes match, only then do we compare the "window" to the
`pattern`. String comparisons are linear because they compare each character to
each character one at a time. But because we only compare strings when are
hashes match (a check which runs in constant time), this spares us the
performance hit.
Diffstat (limited to 'lisp/f')
0 files changed, 0 insertions, 0 deletions