hi Minotauruas, "For each node in the tree query the hash table. If there is a collision (value exists) get point to that node from the table and traverse the subtree, until you reach leaf nodes or find that the subtrees are not the same."
can you explain this above statement in an bit more clearer way.. TIA On Thu, Jul 29, 2010 at 3:37 AM, Minotauraus <[email protected]> wrote: > I'd say use a hash table to store node/pointer for quick lookup > instead. > For each node in the tree query the hash table. If there is a > collision (value exists) get point to that node from the table > and traverse the subtree, until you reach leaf nodes or find that the > subtrees are not the same. > > For large trees you'll end up traversing them to convert it to a > prefix notation and then probably spend (worst case) O(n^2) time > in finding matches. > > To make comparisons faster you could store number of immediate child > nodes for comparison. If number is not the same, subtrees aren't, move > on. > > -Minotauruas. > > On Jul 27, 9:02 am, Harsha Nagesh <[email protected]> wrote: > > Hi, > > > > Given a string, I am interested in finding all repeated substrings > > of any length (not just the longest substring). Can anybody point me > > to the right algorithm/literature for this problem? > > > > My original problem is finding repeated subtrees in a tree that has > > nodes of different kind. My plan is to convert the tree into a prefix > > notation and solve the above mentioned substring problem. > > > > Thanks > > Harsha > > -- > 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Regards, Sony -- 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.
