- Notifications
You must be signed in to change notification settings - Fork105
Time complexity of methods#166
-
Hi, are there any time complexity guarantees for methods? |
BetaWas this translation helpful?Give feedback.
All reactions
Overlapping search only works with standard match semantics, which report matches as they're found.This is discussed a bit in the context of Hyperscan in rebar. In particular, overlapping iteration uses state from the previous search, so it knows where to pick back up in both the haystack and the automaton. Inaho-corasick, there are no wildcards to delay a match being reported or any other way to forceaho-corasick to search the entire remaining haystack on each successive iteration.
The docs could probably use some beefing up with time complexity guarantees, but there in general shouldn't be any surprises here.
Replies: 1 comment
-
Overlapping search only works with standard match semantics, which report matches as they're found.This is discussed a bit in the context of Hyperscan in rebar. In particular, overlapping iteration uses state from the previous search, so it knows where to pick back up in both the haystack and the automaton. In The docs could probably use some beefing up with time complexity guarantees, but there in general shouldn't be any surprises here. |
BetaWas this translation helpful?Give feedback.