use strict;
use warnings;

# set 1
my $st1 = 'SALMWN DE EGENNHSEN TON BOOZ EK THS RAXAB BOOZ DE EGENNHSEN
+ TON WBHD EK THS ROUQ WBHD DE EGENNHSEN TON IESSAI';
my $st2 = 'SALMWN DE EGENNHSEN TON BOES EK THS RAXAB BOES DE EGENNHSEN
+ TON IWBHD EK THS ROUQ IWBHD DE EGENNHSEN TON IESSAI';

# set 2
my $st3 = 'IOUDAS DE EGENNHSEN TON FARES KAI TON ZARA EK THS QAMAR FAR
+ES DE EGENNHSEN TON ESRWM ESRWM DE EGENNHSEN TON ARAM';
my $st4 = 'IOUDAS DE EGENNHSEN TON FARES KAI TON ZARA EK THS QAMAR FAR
+ES DE EGENNHSEN TON ESRWM ESRWM DE EGENNHSEN TON ARAM';

# section 1
my @test1 = all($st3, $st4);
foreach my $t1 (@test1){
    print "$t1\n";
}

# section 2
print "\n\n\n";
my @test2 = all($st1, $st2);
foreach my $t2 (@test2){
    print "$t2\n";
}

sub all {

    my ($str1, $str2) = @_;
    my @s1 = split(/\s+/, $str1);
    my @s2 = split(/\s+/, $str2);    
    my @matrix = ();
    my %substrings = ();
    my $id = 0;
    
    for(my $i=0; $i <= $#s2; $i++){
            for(my $j=0; $j <= $#s1; $j++){
                    if( "$s1[$j]" eq "$s2[$i]"){
                            if( $i == 0 || $j == 0){
                                    $matrix[$i][$j] = 1;
                            } else {
                                    $matrix[$i][$j] = $matrix[$i-1][$j
+-1] + 1;
                                    if( $i == $#s2 || $j == $#s1 ){
                                        $substrings{$id}[0]    = $j-$m
+atrix[$i][$j]+1;
                                        $substrings{$id}[1]    = $j;
                                        $substrings{$id}[2]    = $i-$m
+atrix[$i][$j]+1;
                                        $substrings{$id}[3]    = $i;
                                        $id++;
                                    }
                            }
                    } else {
                            $matrix[$i][$j] = 0;
                             if( $i != 0 && $j != 0 && $matrix[$i-1][$
+j-1] != 0){
                                       $substrings{$id}[0] = $j-$matri
+x[$i-1][$j-1];
                                       $substrings{$id}[1] = $j-1;
                                       $substrings{$id}[2] = $i-$matri
+x[$i-1][$j-1];
                                       $substrings{$id}[3] = $i-1;
                                       $id++;
                             }
                    }
            }
    }    
    my @substr_mat = ();
    my $substr_tmp1 = ();
    my $substr_tmp2 = ();
    my $start = ();
    my $end = ();    
    my %map1 = ();
    my %map2 = ();
    my $m = 0;
    
    foreach my $str (sort {($substrings{$b}[1]-$substrings{$b}[0]) <=>
+ ($substrings{$a}[1]-$substrings{$a}[0]) || $substrings{$a}[0] <=> $s
+ubstrings{$b}[0]} keys %substrings){            
        $substr_tmp1 = '';
        $substr_tmp2 = '';
        
        $start = -1; $end = -1;
        for( my $i = $substrings{$str}[0]; $i <= $substrings{$str}[1];
+ $i++){
            if( ! exists $map1{$i}){
                   $map1{$i} = 1;
                $substr_tmp1 .= "$s1[$i] ";
                if($start == -1){
                    $start = $end = $i;
                } else {
                    $end = $i;
                }
            }
           }
        next if $start == -1;
        
        $start = -1; $end = -1;
        for( my $i = $substrings{$str}[2]; $i <= $substrings{$str}[3];
+ $i++){
            if( ! exists $map2{$i}){
                   $map2{$i} = 1;
                $substr_tmp2 .= "$s2[$i] ";
                if($start == -1){
                    $start = $end = $i;
                } else {
                    $end = $i;
                }
            }
           }
        next if $start == -1;
        
        if( length($substr_tmp1) <= length($substr_tmp2) ){
            $substr_mat[$m++] = $substr_tmp1;
        } else {
                $substr_mat[$m++] = $substr_tmp2;
        }        
    }
    return @substr_mat;    
}
[download]