On Thu, Feb 14, 2002 at 05:54:01PM +0000, Stephen Turner wrote:
> No doubt the experts will be along with a slicker way soon...
I think the following should work, except maybe in the irksome
case the two strings only share one letter thatis at the end of
the second string. There's also probably ways to optimize
it (by choosing which string will be $string and which one will
be @bank, and stuff like that):
sub lcs
{
my $string = shift;
my @bank = split //, shift;
my( $longuest, $snippet );
while( @bank )
{
$snippet .= shift @bank
while -1 < index $string, "$snippet$bank[0]" and @bank;
if( -1 == index $string, $snippet )
{
$snippet = shift @bank;
redo;
}
else
{
$longuest = $snippet if length $longuest < length $snippet;
substr( $snippet, 0, 1 ) = '';
$snippet .= shift @bank;
}
}
return $longuest;
}
# Testing
$\ = "\n";
print lcs("This is one piece of text", "Another piece of text here");
print lcs("Another piece of text here", "This is one piece of text");
print lcs("bbbbcccbbbd", "dbbbbeeebbbf");
print lcs("abbbbcccbbbd", "bbbbeeebbbf");
print lcs("aaaabcd", "dfhaaaa");
print lcs("dfhaaaa", "aaaabcd");
print lcs("abcd", "efgh");
`/anick
--
The whole secret of life is to be interested in one thing
profoundly and in a thousand other things well. - Hugh Walpole
