search

jmeaster30 / vore

VerbOse Regular Expressions - Regular Expression Engine with Verbose English-like Syntax
MIT License
1 stars 0 forks source link

Jump further than 1 character on failed matches #79

Open jmeaster30 opened 1 year ago

jmeaster30 commented 1 year ago

Currently, when an expression fails to match it goes back to the offset that we started at and starts the next round of matching at the very next character. This is inefficient since if we are looking for 'abc' and failed on 'def' then we can skip all of those characters.

I was imagining something like Rabin-Karp or Knuth-Morris-Pratt string search algorithms

jmeaster30 commented 1 year ago

The algorithm I was thinking of was Knuth Morris Pratt. It definitely can be extended to work with our use case. I think some of the other optimizations I have planned will assist with this.

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm