# Data structure for storing strings

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

• How do you know that such a data structure exists? – Yuval Filmus Oct 11 at 15:42
• @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. – kevin Oct 11 at 15:50
• @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. – kevin Oct 11 at 20:54
• The running time $O(\log m \cdot \log n)$ would imply that you cannot read every character of the query string. This seems unreasonable. – Daniel Oct 11 at 21:42