Let $n$ be the number of strings which are sorted in lexicographical order and stored in a balanced binary search tree. You are provided with a prefix $x$ of which $M$ strings have the prefix $x$. I have devised the following algorithm, where I search until I find the first occurence of the prefix $x$ in one of the nodes. After that I run an inorder traversal on it, such that I print only the ones, that have prefix $x$ and are in order.
For example of sorted strings: $[ACT,BAT,CAT,CAB]$ and the prefix $x = CA$, I would print $CAT$ and $CAB$.
Asked By : user1675999
Answered By : Joe
The data structure you are looking for is called a range tree. Range trees are usually used for geometric data, but they can be used here as well. In 1d, a range tree is simply a balanced binary search tree with the data stored at the leaves and the internal nodes augmented with the min and max element stored in the subtree. They have running time $O(\log n+ k) $ where $n$ is the total number of objects in the tree and $k$ is the number of objects reported. You will have to structure your queries slightly differently to use a range instead if a prefix. So add a special min and max character to your alphabet, call them 0 and 1 for convenience. Now to find all strings with prefix "CA", " you would search for all strings in the range (CA0, CA1).
As noted in the comments above, a trie is the structure one would normally use for this type or query. But the computational model used is slightly different, so it's hard to compare. The running time would be the length of your longest output string + k.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6368
0 comments:
Post a Comment
Let us know your responses and feedback