my @a= qw( a b c e h j l m n p ); my @b= qw( b c d e f j k l m r s t ); my @diff= easy( \@a, \@b ); #### # @a @b @a @b # same? range range values values ( 0, 0=>0, 0=>-1, # a ! 1, 1=>2, 0=> 1, # b c = b c 0, 3=>2, 2=> 2, # ! d 1, 3=>3, 3=> 3, # e = e 0, 4=>4, 4=> 4, # f ! h 1, 5=>5, 5=> 5, # j = j 0, 6=>5, 6=> 6, # ! k 1, 6=>7, 7=> 8, # l m = l m 0, 8=>9, 9=>11, # n p ! r s t ); #### my @a= qw( a b c e h j l m n p ); my @b= qw( b c d e f j k l m r s t ); my $diff= easy( \@a, \@b ); while( @$diff ) { my( $same, $aMin, $aMax, $bMin, $bMax )= splice @$diff, 0, 5; my $a= join "", @a[$aMin..$aMax]; if( $same ) { print $a; } else { print "$a" if "" ne $a; my $b= join "", @b[$bMin..$bMax]; print "$b" if "" ne $b; } } #### abcdehfjklmnprst #### $_ .= $/ for @a, @b; my $diff= easy( \@a, \@b ); while( @$diff ) { my( $same, $aMin, $aMax, $bMin, $bMax )= splice @$diff, 0, 5; if( $same ) { for( @a[$aMin..$aMax] ) { print " $_"; } } else { for( @a[$aMin..$aMax] ) { print "-$_"; } for( @b[$bMin..$bMax] ) { print "+$_"; } } } #### -a b c +d e -h +f j +k l m -n -p +r +s +t #### my $diff= easy( \@a, \@b ); while( @$diff ) { my( $same, $aMin, $aMax, $bMin, $bMax )= splice @$diff, 0, 5; $_++ for $aMin, $aMax, $bMin, $bMax; next if $same; my $sep= ''; if( $bMax < $bMin ) { print "$aMin,$aMax","d$bMax\n"; } elsif( $aMax < $aMin ) { print "$aMax","a$bMin,$bMax\n"; } else { $sep= "---\n"; print "$aMin,$aMax","c$bMin,$bMax\n"; } for( @a[$aMin-1..$aMax-1] ) { print "< $_"; } print $sep; for( @b[$bMin-1..$bMax-1] ) { print "> $_"; } } #### 1,1d0 < a 3a3,3 > d 5,5c5,5 < h --- > f 6a7,7 > k 9,10c10,12 < n < p --- > r > s > t #### sub easy { my $a= shift; # array ref my $b= shift; # array ref my @diff= ( 1, 0, -1, 0, -1 ); traverse_sequences( $a, $b, { MATCH => sub { my( $aEnd, $bEnd )= @_; $_++ for my( $aTop, $bTop )= @diff[ 2-5, 4-5 ]; if( $aTop < $aEnd || $bTop < $bEnd ) { push @diff, 0, $aTop, $aEnd-1, $bTop, $bEnd-1, 1, $aEnd, $aEnd, $bEnd, $bEnd; } else { @diff[ 2-5, 4-5 ]= ( $aEnd, $bEnd ); } }, }, @_ ); my( $aEnd, $bEnd )= ( 0+@$a, 0+@$b ); $_++ for my( $aTop, $bTop )= @diff[ 2-5, 4-5 ]; if( $aTop < $aEnd || $bTop < $bEnd ) { push @diff, 0, $aTop, $aEnd-1, $bTop, $bEnd-1; } splice @diff, 0, 5 if $diff[2] < 0 && $diff[4] < 0; return wantarray ? @diff : \@diff; }