hw search substring in a list of indexed strings?

Question

i am implementing dictionary in which key is a string keyword.suppose i have following keys in dictionary.

mat**hon** sat**hon** lat**hon**

now if i serach single keyword suppose mathon it will search it in constant time.but if i am to search hon i want all of three words to be retreived in constant time or minimum time possible like in case of google search.what should be my approach? and is dictionary right datastructure for purpose?

value of dictionary is list of items which i need to display to user and search can be multiple keyword based.

Answer 1

a gaddag, as described in this paper, is probably your best bet. it's a variant on a trie that lets you start searching anywhere in a word, and walks both forwards and backwards. it's not O(1) lookup, but it's pretty fast and has a reasonable space usage.

edit: and for multiple keywords, you can simply search individually on each keyword and then do a set intersection or union depending. it's likely faster than you think; at the very least worth implementing as the simplest-possible-algorithm and discarding only if it proves to be an actual bottleneck when profiling.