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 24th, 2007, 7:18am)

Title: Longest repeated String in two strings
Post by downloadprj on Nov 24th, 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 26th, 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 27th, 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 27th, 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 27th, 2007, 11:22am
@Towr
yes u r right... :D



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board