News for hackers. Stuff that matters.

A comment on Dictionary of Algorithms and Data Structures (1998). Parent comment

Re:Dictionary of Algorithms and Data Structures (1998) by justin66 on Friday October 21, 2016 @09:02AM (#12760023)
Searching a new string - adding a string to the set - would require comparing against all items in the set, yes. That's a much less daunting prospect than what you said: You really have to scan your complete dataset on every search.

Building the index, or adding to it, is not fast (without some heuristics applied) but searching using the index isn't bad.

[ Parent | on HN ]
Re:Dictionary of Algorithms and Data Structures (1998) by amelius on Friday October 21, 2016 @12:50PM (#12762056)
Okay, now I understand what you meant.

But what if a search needs to be fast regardless of whether the string has been searched for before?

[ Parent | on HN ]
Re:Dictionary of Algorithms and Data Structures (1998) by justin66 on Friday October 21, 2016 @12:57PM (#12762156)
I thought the thing peff briefly described above sounded pretty good. The worst case complexity, if I'm visualizing it right, would be the length of the string you were comparing.

I remember some discussion of this in previous HN threads but I don't know what it was about...

[ Parent | on HN ]