"longest common substring in the given string".
If i get it right. You need two strings to find a common subsequence.
We use DP for it.
2010/8/18 ♪ ѕяiηivαѕαη ♪ <21.sr...@gmail.com>
> Example:
> If my sequence is ABC..the longest common subsequence is
> AC,BC,AB.
> It is a very common problem...
Example:
If my sequence is ABC..the longest common subsequence is
AC,BC,AB.
It is a very common problem...
On Wed, Aug 18, 2010 at 11:58 AM, vinodh kumar wrote:
> heh could u explain the question with a example..??!!
>
> On Aug 18, 8:47 pm, ♪ ѕяiηivαѕαη ♪ <21.sr...@gmail.com> wrote:
> > Hi..
> >
heh could u explain the question with a example..??!!
On Aug 18, 8:47 pm, ♪ ѕяiηivαѕαη ♪ <21.sr...@gmail.com> wrote:
> Hi..
> Can anyone here explain me /provide me with an algorithm/source code in C
> which efficiently finds out the *longest common substring in the given
> string??*
--
You rec
Thank you, Gene.
Although I dont really understand perl language, I can figure out that
your code is about a top-down strategy with memoization. But I cannot
find the "b" table which is used for the common sequences storage,
maybe because of my inacquaintance with perl language.
Can you give me an
In perl (hopefully the homework has been due already)...
use strict;
our %memo;
sub lcs {
my ($x, $y) = @_;
my $key = "$x|$y";
return $memo{$key} if defined $memo{$key};
my $s = '';
for (my $i = 0; $i < length($x); $i++) {
for (my $j = 0; $j < length($y); $j++) {
if (subs
you can store the two strings in an upside down suffix tree. a simple
edge scan of common path will give you all possible (and largest)
common substring
LCS(X, Y) =
the longest string over i =1..|X| and j=1..|Y| where X[i]=Y[j] given
by
LCS(X[1..i-1], Y[1..j-1]) + X[i] + LCS(X[i+1..|X|], Y[j+1..|Y|]
