diff options
author | William Carroll <wpcarro@gmail.com> | 2020-11-16T17·14+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-11-16T17·14+0000 |
commit | 6989c3a91a99d18fbe527fd453e2f1f9a5a1c1af (patch) | |
tree | a16408275f3b5f884f099f6c880f58835779ece4 /lisp/f | |
parent | a2fa88f5611f878c6937abaab4f6858a203c37b6 (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