OK, this seems to be one way to do it, if I've understood the problem
correctly. No doubt the experts will be along with a slicker way soon...
#!/usr/bin/perl
sub lcs {
my($l,$off1,$off2,$i,$a,$b);
local $_;
for $i(-length($_[0])+1..length($_[1])-1) {
$a=($i>0)?$_[0]:substr($_[0],-$i);
$b=($i>0)?substr($_[1],$i):$_[1];
$_=$a^$b;
while(/\0+/g) {
if(length$&>$l){
$l=length$&;
$off1=$i;
$off2=$-[0]
}
}
}
if ($l == 0) { print("No common substring\n"); }
else {
print("Longest common substring of length $l:\n\"");
print(substr($_[0], ($off1>0)?$off2:$off2-$off1, $l), "\"\n");
print("Occurring in 1st string at position ",
(($off1>0)?$off2:$off2-$off1)+1, "\n");
print("and in 2nd string at position ",
(($off1>0)?$off2+$off1:$off2)+1, "\n\n");
}
}
# Testing
lcs("This is one piece of text", "Another piece of text here");
lcs("Another piece of text here", "This is one piece of text");
lcs("bbbbcccbbbd", "dbbbbeeebbbf");
lcs("abbbbcccbbbd", "bbbbeeebbbf");
lcs("aaaabcd", "dfhaaaa");
lcs("dfhaaaa", "aaaabcd");
lcs("abcd", "efgh");
--
Stephen Turner, Cambridge, UK http://homepage.ntlworld.com/adelie/stephen/
"This is Henman's 8th Wimbledon, and he's only lost 7 matches." BBC, 2/Jul/01
