Use suffix trie. On 30 July 2010 00:50, Sony Jose <[email protected]> wrote:
> 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- regards, soumya prasad ukil -- 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.
