@t3rminal: k On Wed, Jun 15, 2011 at 7:05 AM, Terence <[email protected]> wrote:
> Traversal the suffix tree is enough. > All substrings from root to leaf (including at least 1 character of leaf > node) occur only once. > Choose the shortest among them. > > > > On 2011-6-15 5:28, T3rminal wrote: > >> @bittu >> How can u find the shortest substring from the tree in 0(n). Can u >> please elaborate a bit ? >> >> On Jun 14, 6:03 pm, bittu<[email protected]> wrote: >> >>> I found one interesting question >>> >>> Given a string s , return the shortest substring that is >>> only occurring once. >>> Examples: >>> s="aabbabbaab" gives either "bab" or "baa" >>> s="aaaa" gives "aaaa" >>> >>> My Approaches >>> >>> Generate All Possible SubStrings O(N^2) >>> puts all substrings into hashtable& keep incrementing counter for >>> each substring , return substring with counter 1 memory O(N) >>> Not efficient >>> >>> Create Suffix Tree Seems to be Efficient Solution Only You Need to do >>> Create Tree& then we can find the >>> shortest substring that is only occurring once. in O(n) time >>> >>> PS: let me other approaches,suggestion >>> >>> Thanks >>> Shashank >>> CSE,BIT Mesra >>> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- AKSHAY RASTOGI BE(Hons) CS BITS PILANI , Pilani -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
