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<shashank7andr...@gmail.com> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
