Have Geek Brain

Hw search substring in a list of indexed strings?

I am using a dictionary where the key is the string keyword. Suppose I have the following keys in a dictionary.

mat hon sb hon lat hon

now if i serach one keyword suppose mathon will look for it at constant time. But if I search for hon , I want all three words to be removed at constant time or minimum time, like in the case of a google search. What should be my approach? and is the dictionary data structure for purposes?

The dictionary value is a list of items that I need to display to the user, and the search can be based on multiple keywords.

+1


a source to share


1 answer


a gaddag as described in this article is probably your best bet. it is a trie variant that allows you to start searching anywhere in one word and walk both forward and backward. it's not an O (1) search, but it's pretty fast and has a reasonable use of space.



edit: and for multiple keywords, you can just search individually for each keyword and then do a set of intersections or join depending on. it is faster than you think; at the very least, it should be implemented as the simplest possible algorithm and abandoned only if it turns out to be an actual bottleneck in profiling.

+1


a source






More articles:


All Articles