use strict; use warnings; use Data::Dumper; # word lists, first element a dummy my @s1 = (q{}, split(/s+/, "Perlmonks is the best perl community")); my @s2 = (q{}, split(/s+/, "Perlmonks is one of the best community of perl users")); my @M; #init dyn. prog. matrix for my $i ( 0 .. $#s1) { $M[$i][0] = 0; } for my $i ( 0 .. $#s2) { $M[0][$i] = 0; } #calc lcs (word based) for my $i ( 1 .. $#s1) { for my $j ( 1 .. $#s2) { if ($s1[$i] eq $s2[$j]) { $M[$i][$j] = $M[$i-1][$j-1]+1; } else { if ($M[$i][$j-1] > $M[$i-1][$j]) { $M[$i][$j] = $M[$i][$j-1]; } else { $M[$i][$j] = $M[$i-1][$j]; } } } } #print Dumper \@M; printDiff($#s1, $#s2); sub printDiff { my ($i, $j) = @_; if ($i > 0 && $j > 0 and $s1[$i] eq $s2[$j]) { printDiff($i-1, $j-1); print " " . $s1[$i]; } else { if ($j > 0 && ($i == 0 || $M[$i][$j-1] >= $M[$i-1][$j])) { printDiff($i, $j-1); print " <" . $s2[$j] . ">"; } elsif ($i > 0 && ($j == 0 || $M[$i][$j-1] < $M[$i-1][$j])) { printDiff($i-1, $j); print " [" . $s1[$i] . "]"; } } }