wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Longest repeated String in two strings
        
(Message started by: downloadprj on Nov 24^th, 2007, 7:18am)

Title: Longest repeated String in two strings
Post by downloadprj on Nov 24^th, 2007, 7:18am

Find the longest repeated string in two strings.
It has to be a contiguous string in both.
e.g.
str1 = "bdhalgorithmseh"
str2 = "sdalgorithmqgf"

Result = "algorithm"

Title: Re: Longest repeated String in two strings
Post by KWillets on Nov 26^th, 2007, 11:10am

http://en.wikipedia.org/wiki/Longest_common_substring

Title: Re: Longest repeated String in two strings
Post by johny_cage on Nov 27^th, 2007, 7:03am

@Link above

Can anybody please elaborate, that how the suffix tree leaves are having the values (x:y). It is confusing....

Title: Re: Longest repeated String in two strings
Post by towr on Nov 27^th, 2007, 7:10am

I think in x:y x represent the id# of the string, and y the position in that string where the match starts.
So e.g. in that diagram, "A$" occurs at position 3 of strings 1 (BABA) and 2 (ABBA)

Title: Re: Longest repeated String in two strings
Post by johny_cage on Nov 27^th, 2007, 11:22am

@Towr
yes u r right... :D