1
$\begingroup$

I'm designing a tree data structure to store strings in. One classic solution is prefix tree, but I am looking for a solution that the time to check if the string is in the storage is O(logm*logn) where m is the length of the string and n is the total number of character in Alphabet(if the string can be lower case aliphatic a-z only, n is 26).

I checked this post Data structure for storing strings, but the solution of prefix tree will take O(m) to insert.

Can I get some idea about the data structure with O(logm * logn) traverse and O(n * logm) insert time? Any general design ideas will be appreciated!

Thanks

$\endgroup$
  • $\begingroup$ How do you know that such a data structure exists? $\endgroup$ – Yuval Filmus Oct 11 at 15:42
  • $\begingroup$ @YuvalFilmus It is a research and coding question in assignment, so I am sure it exists. I got stucked, I want to ask for some general ideas to get start. It is possible since the insert time is sacrificed. $\endgroup$ – kevin Oct 11 at 15:50
  • $\begingroup$ @Gilles n is the size of unique characters in all strings. For example, if the string can contain only low case letter n is 26. If the string can contain both lower and upper letter and numbers, the n is 26 + 26 + 10 =62. $\endgroup$ – kevin Oct 11 at 20:54
  • 1
    $\begingroup$ The running time $O(\log m \cdot \log n)$ would imply that you cannot read every character of the query string. This seems unreasonable. $\endgroup$ – Daniel Oct 11 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.