i was given a set(no duplication then) of binary strings with arbitrary lenght and number, and need to find out if there is any string is the prefix of other string. for small set and string with small length, it's easy, just build a binary tree by read in each string, whenever i find a prefix match, i m done.but with a lots of strings with long length, this method won't be efficient. just wondering what would be the right data structure and algorithm for this one. huffman tree? tries(radix tree)? or anything? thanks.
A:
I would go with a trie. Using a trie, insert all the strings, such that the last node of each string is marked with a flag, then for each string, walk along its path and check if any node on the page has its flag set. If yes, then the string ending at that node is a prefix of the string you're analyzing.
Assuming n = number of strings and k = average length, inserting and analyzing both take O(kn) in total.
A prefix tree (a trie with nodes longer than a single character) might be more efficient, but not as easy to implement.
Max Shawabkeh
2010-01-31 06:18:57