Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Time complexity of methods#166

AnsweredbyBurntSushi
Ruttie2006 asked this question inQ&A
Discussion options

Hi, are there any time complexity guarantees for methods?
I'm mainly interested in if find_overlapping_iter has a complexity risk of O(mn²) similar to the regex crate's iter methods.
I could verify that find_iter doesn't have this issue by looking at the code, but unfortunately overlapping iter goes a bit too deep into the automaton details for me to fully grasp

You must be logged in to vote

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

Comment options

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.

You must be logged in to vote
0 replies
Answer selected byBurntSushi
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Category
Q&A
Labels
None yet
2 participants
@Ruttie2006@BurntSushi

[8]ページ先頭

©2009-2025 Movatter.jp