line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package LCS; |
2
|
|
|
|
|
|
|
|
3
|
2
|
|
|
2
|
|
16104
|
use strict; |
|
2
|
|
|
|
|
6
|
|
|
2
|
|
|
|
|
101
|
|
4
|
2
|
|
|
2
|
|
11
|
use warnings; |
|
2
|
|
|
|
|
3
|
|
|
2
|
|
|
|
|
73
|
|
5
|
|
|
|
|
|
|
|
6
|
2
|
|
|
2
|
|
57
|
use 5.006; |
|
2
|
|
|
|
|
5
|
|
|
2
|
|
|
|
|
121
|
|
7
|
|
|
|
|
|
|
our $VERSION = '0.09'; |
8
|
|
|
|
|
|
|
|
9
|
2
|
|
|
2
|
|
570
|
use Data::Dumper; |
|
2
|
|
|
|
|
6870
|
|
|
2
|
|
|
|
|
3398
|
|
10
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
sub new { |
12
|
6
|
|
|
6
|
1
|
1048
|
my $class = shift; |
13
|
|
|
|
|
|
|
# uncoverable condition false |
14
|
6
|
100
|
66
|
|
|
50
|
bless @_ ? @_ > 1 ? {@_} : {%{$_[0]}} : {}, ref $class || $class; |
|
2
|
100
|
|
|
|
19
|
|
15
|
|
|
|
|
|
|
} |
16
|
|
|
|
|
|
|
|
17
|
|
|
|
|
|
|
|
18
|
|
|
|
|
|
|
sub lcs2align { |
19
|
63
|
|
|
63
|
1
|
136
|
my ($self, $X, $Y, $LCS) = @_; |
20
|
|
|
|
|
|
|
|
21
|
63
|
|
|
|
|
68
|
my $hunks = []; |
22
|
|
|
|
|
|
|
|
23
|
63
|
|
|
|
|
93
|
my $Xcurrent = -1; |
24
|
63
|
|
|
|
|
65
|
my $Ycurrent = -1; |
25
|
63
|
|
|
|
|
45
|
my $Xtemp; |
26
|
|
|
|
|
|
|
my $Ytemp; |
27
|
|
|
|
|
|
|
|
28
|
63
|
|
|
|
|
81
|
for my $hunk (@$LCS) { |
29
|
253
|
|
100
|
|
|
748
|
while ( ($Xcurrent+1 < $hunk->[0] || $Ycurrent+1 < $hunk->[1]) ) { |
30
|
125
|
|
|
|
|
140
|
$Xtemp = ''; |
31
|
125
|
|
|
|
|
86
|
$Ytemp = ''; |
32
|
125
|
100
|
|
|
|
199
|
if ($Xcurrent+1 < $hunk->[0]) { |
33
|
93
|
|
|
|
|
72
|
$Xcurrent++; |
34
|
93
|
|
|
|
|
98
|
$Xtemp = $X->[$Xcurrent]; |
35
|
|
|
|
|
|
|
} |
36
|
125
|
100
|
|
|
|
202
|
if ($Ycurrent+1 < $hunk->[1]) { |
37
|
59
|
|
|
|
|
38
|
$Ycurrent++; |
38
|
59
|
|
|
|
|
60
|
$Ytemp = $Y->[$Ycurrent]; |
39
|
|
|
|
|
|
|
} |
40
|
125
|
|
|
|
|
449
|
push @$hunks,[$Xtemp,$Ytemp]; |
41
|
|
|
|
|
|
|
} |
42
|
|
|
|
|
|
|
|
43
|
253
|
|
|
|
|
239
|
$Xcurrent = $hunk->[0]; |
44
|
253
|
|
|
|
|
191
|
$Ycurrent = $hunk->[1]; |
45
|
253
|
|
|
|
|
526
|
push @$hunks,[$X->[$Xcurrent],$Y->[$Ycurrent]]; # elements |
46
|
|
|
|
|
|
|
} |
47
|
63
|
|
100
|
|
|
215
|
while ( ($Xcurrent+1 <= $#$X || $Ycurrent+1 <= $#$Y) ) { |
48
|
68
|
|
|
|
|
66
|
$Xtemp = ''; |
49
|
68
|
|
|
|
|
60
|
$Ytemp = ''; |
50
|
68
|
100
|
|
|
|
102
|
if ($Xcurrent+1 <= $#$X) { |
51
|
51
|
|
|
|
|
39
|
$Xcurrent++; |
52
|
51
|
|
|
|
|
45
|
$Xtemp = $X->[$Xcurrent]; |
53
|
|
|
|
|
|
|
} |
54
|
68
|
100
|
|
|
|
100
|
if ($Ycurrent+1 <= $#$Y) { |
55
|
38
|
|
|
|
|
29
|
$Ycurrent++; |
56
|
38
|
|
|
|
|
40
|
$Ytemp = $Y->[$Ycurrent]; |
57
|
|
|
|
|
|
|
} |
58
|
68
|
|
|
|
|
244
|
push @$hunks,[$Xtemp,$Ytemp]; |
59
|
|
|
|
|
|
|
} |
60
|
63
|
|
|
|
|
188
|
return $hunks; |
61
|
|
|
|
|
|
|
} |
62
|
|
|
|
|
|
|
|
63
|
|
|
|
|
|
|
sub sequences2hunks { |
64
|
72
|
|
|
72
|
1
|
37880
|
my ($self, $a, $b) = @_; |
65
|
72
|
|
|
|
|
163
|
return [ map { [ $a->[$_], $b->[$_] ] } 0..$#$a ]; |
|
519
|
|
|
|
|
923
|
|
66
|
|
|
|
|
|
|
} |
67
|
|
|
|
|
|
|
|
68
|
|
|
|
|
|
|
sub hunks2sequences { |
69
|
24
|
|
|
24
|
1
|
30
|
my ($self, $hunks) = @_; |
70
|
|
|
|
|
|
|
|
71
|
24
|
|
|
|
|
37
|
my $a = []; |
72
|
24
|
|
|
|
|
23
|
my $b = []; |
73
|
|
|
|
|
|
|
|
74
|
24
|
|
|
|
|
40
|
for my $hunk (@$hunks) { |
75
|
173
|
|
|
|
|
203
|
push @$a, $hunk->[0]; |
76
|
173
|
|
|
|
|
201
|
push @$b, $hunk->[1]; |
77
|
|
|
|
|
|
|
} |
78
|
24
|
|
|
|
|
126
|
return ($a,$b); |
79
|
|
|
|
|
|
|
} |
80
|
|
|
|
|
|
|
|
81
|
|
|
|
|
|
|
sub align2strings { |
82
|
48
|
|
|
48
|
1
|
53
|
my ($self, $hunks,$gap) = @_; |
83
|
|
|
|
|
|
|
#$gap //= '_'; |
84
|
48
|
100
|
|
|
|
94
|
$gap = (defined $gap) ? $gap : '_'; |
85
|
|
|
|
|
|
|
|
86
|
48
|
|
|
|
|
50
|
my $a = ''; |
87
|
48
|
|
|
|
|
51
|
my $b = ''; |
88
|
|
|
|
|
|
|
|
89
|
48
|
|
|
|
|
70
|
for my $hunk (@$hunks) { |
90
|
346
|
|
|
|
|
715
|
my ($ae,$be) = $self->fill_strings($hunk->[0],$hunk->[1],$gap); |
91
|
346
|
|
|
|
|
319
|
$a .= $ae; |
92
|
346
|
|
|
|
|
395
|
$b .= $be; |
93
|
|
|
|
|
|
|
} |
94
|
48
|
|
|
|
|
244
|
return ($a,$b); |
95
|
|
|
|
|
|
|
} |
96
|
|
|
|
|
|
|
|
97
|
|
|
|
|
|
|
sub fill_strings { |
98
|
351
|
|
|
351
|
1
|
856
|
my ($self, $string1,$string2, $gap) = @_; |
99
|
|
|
|
|
|
|
#$gap //= '_'; |
100
|
351
|
100
|
|
|
|
433
|
$gap = (defined $gap) ? $gap : '_'; |
101
|
|
|
|
|
|
|
|
102
|
1
|
|
|
1
|
|
10
|
my @m = $string1 =~ m/(\X)/g; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
40
|
|
|
351
|
|
|
|
|
1186
|
|
103
|
351
|
|
|
|
|
18651
|
my @n = $string2 =~ m/(\X)/g; |
104
|
351
|
|
|
|
|
482
|
my $max = max(scalar(@m),scalar(@n)); |
105
|
351
|
100
|
|
|
|
684
|
if ($max - scalar(@m) > 0) { |
106
|
29
|
|
|
|
|
50
|
for (1..$max-scalar(@m)) { |
107
|
29
|
|
|
|
|
60
|
$string1 .= $gap; |
108
|
|
|
|
|
|
|
} |
109
|
|
|
|
|
|
|
} |
110
|
351
|
100
|
|
|
|
501
|
if ($max - scalar(@n) > 0) { |
111
|
71
|
|
|
|
|
106
|
for (1..$max-scalar(@n)) { |
112
|
72
|
|
|
|
|
134
|
$string2 .= $gap; |
113
|
|
|
|
|
|
|
} |
114
|
|
|
|
|
|
|
} |
115
|
351
|
|
|
|
|
661
|
return ($string1,$string2); |
116
|
|
|
|
|
|
|
} |
117
|
|
|
|
|
|
|
|
118
|
|
|
|
|
|
|
sub LLCS { |
119
|
24
|
|
|
24
|
1
|
45871
|
my ($self,$X,$Y) = @_; |
120
|
|
|
|
|
|
|
|
121
|
24
|
|
|
|
|
34
|
my $m = scalar @$X; |
122
|
24
|
|
|
|
|
30
|
my $n = scalar @$Y; |
123
|
|
|
|
|
|
|
|
124
|
24
|
|
|
|
|
34
|
my $c = []; |
125
|
|
|
|
|
|
|
|
126
|
24
|
|
|
|
|
47
|
for my $i (0..1) { |
127
|
48
|
|
|
|
|
55
|
for my $j (0..$n) { |
128
|
326
|
|
|
|
|
389
|
$c->[$i][$j]=0; |
129
|
|
|
|
|
|
|
} |
130
|
|
|
|
|
|
|
} |
131
|
|
|
|
|
|
|
|
132
|
24
|
|
|
|
|
26
|
my ($i,$j); |
133
|
|
|
|
|
|
|
|
134
|
24
|
|
|
|
|
59
|
for ($i=1; $i <= $m; $i++) { |
135
|
159
|
|
|
|
|
233
|
for ($j=1; $j <= $n; $j++) { |
136
|
2984
|
100
|
|
|
|
3582
|
if ($X->[$i-1] eq $Y->[$j-1]) { |
137
|
146
|
|
|
|
|
287
|
$c->[1][$j] = $c->[0][$j-1]+1; |
138
|
|
|
|
|
|
|
} |
139
|
|
|
|
|
|
|
else { |
140
|
2838
|
|
|
|
|
3632
|
$c->[1][$j] = max($c->[1][$j-1],$c->[0][$j]); |
141
|
|
|
|
|
|
|
} |
142
|
|
|
|
|
|
|
} |
143
|
159
|
|
|
|
|
247
|
for ($j = 1; $j <= $n; $j++) { |
144
|
2984
|
|
|
|
|
4932
|
$c->[0][$j] = $c->[1][$j]; |
145
|
|
|
|
|
|
|
} |
146
|
|
|
|
|
|
|
} |
147
|
24
|
|
|
|
|
80
|
return ($c->[1][$n]); |
148
|
|
|
|
|
|
|
} |
149
|
|
|
|
|
|
|
|
150
|
|
|
|
|
|
|
|
151
|
|
|
|
|
|
|
sub LCS { |
152
|
72
|
|
|
72
|
1
|
299715
|
my ($self,$X,$Y) = @_; |
153
|
|
|
|
|
|
|
|
154
|
72
|
|
|
|
|
151
|
my $m = scalar @$X; |
155
|
72
|
|
|
|
|
91
|
my $n = scalar @$Y; |
156
|
|
|
|
|
|
|
|
157
|
72
|
|
|
|
|
141
|
my $c = []; |
158
|
72
|
|
|
|
|
86
|
my ($i,$j); |
159
|
72
|
|
|
|
|
247
|
for ($i=0;$i<=$m;$i++) { |
160
|
549
|
|
|
|
|
868
|
for ($j=0;$j<=$n;$j++) { |
161
|
9918
|
|
|
|
|
15395
|
$c->[$i][$j]=0; |
162
|
|
|
|
|
|
|
} |
163
|
|
|
|
|
|
|
} |
164
|
72
|
|
|
|
|
164
|
for ($i=1;$i<=$m;$i++) { |
165
|
477
|
|
|
|
|
681
|
for ($j=1;$j<=$n;$j++) { |
166
|
8952
|
100
|
|
|
|
10464
|
if ($X->[$i-1] eq $Y->[$j-1]) { |
167
|
438
|
|
|
|
|
948
|
$c->[$i][$j] = $c->[$i-1][$j-1]+1; |
168
|
|
|
|
|
|
|
} |
169
|
|
|
|
|
|
|
else { |
170
|
8514
|
|
|
|
|
10612
|
$c->[$i][$j] = max($c->[$i][$j-1], $c->[$i-1][$j]); |
171
|
|
|
|
|
|
|
} |
172
|
|
|
|
|
|
|
} |
173
|
|
|
|
|
|
|
} |
174
|
72
|
|
|
|
|
252
|
my $path = $self->_lcs($X,$Y,$c,$m,$n,[]); |
175
|
|
|
|
|
|
|
|
176
|
72
|
|
|
|
|
565
|
return $path; |
177
|
|
|
|
|
|
|
} |
178
|
|
|
|
|
|
|
|
179
|
|
|
|
|
|
|
|
180
|
|
|
|
|
|
|
sub max { |
181
|
11707
|
100
|
|
11707
|
1
|
25069
|
($_[0] > $_[1]) ? $_[0] : $_[1]; |
182
|
|
|
|
|
|
|
} |
183
|
|
|
|
|
|
|
|
184
|
|
|
|
|
|
|
|
185
|
|
|
|
|
|
|
sub _lcs { |
186
|
72
|
|
|
72
|
|
115
|
my ($self,$X,$Y,$c,$i,$j,$L) = @_; |
187
|
|
|
|
|
|
|
|
188
|
72
|
|
100
|
|
|
357
|
while ($i > 0 && $j > 0) { |
189
|
519
|
100
|
|
|
|
996
|
if ($X->[$i-1] eq $Y->[$j-1]) { |
|
|
100
|
|
|
|
|
|
190
|
309
|
|
|
|
|
265
|
unshift @{$L},[$i-1,$j-1]; |
|
309
|
|
|
|
|
655
|
|
191
|
309
|
|
|
|
|
263
|
$i--; |
192
|
309
|
|
|
|
|
822
|
$j--; |
193
|
|
|
|
|
|
|
} |
194
|
|
|
|
|
|
|
elsif ($c->[$i][$j] == $c->[$i-1][$j]) { |
195
|
135
|
|
|
|
|
355
|
$i--; |
196
|
|
|
|
|
|
|
} |
197
|
|
|
|
|
|
|
else { |
198
|
75
|
|
|
|
|
213
|
$j--; |
199
|
|
|
|
|
|
|
} |
200
|
|
|
|
|
|
|
} |
201
|
72
|
|
|
|
|
141
|
return $L; |
202
|
|
|
|
|
|
|
} |
203
|
|
|
|
|
|
|
|
204
|
|
|
|
|
|
|
|
205
|
|
|
|
|
|
|
sub _all_lcs { |
206
|
72
|
|
|
72
|
|
103
|
my ($self,$ranks,$rank,$max) = @_; |
207
|
|
|
|
|
|
|
|
208
|
72
|
|
|
|
|
164
|
my $R = [[]]; |
209
|
|
|
|
|
|
|
|
210
|
72
|
|
|
|
|
154
|
while ($rank <= $max) { |
211
|
309
|
|
|
|
|
255
|
my @temp; |
212
|
309
|
|
|
|
|
368
|
for my $path (@$R) { |
213
|
459
|
|
|
|
|
350
|
for my $hunk (@{$ranks->{$rank}}) { |
|
459
|
|
|
|
|
657
|
|
214
|
765
|
100
|
100
|
|
|
500
|
if (scalar @{$path} == 0) { |
|
765
|
100
|
|
|
|
2739
|
|
215
|
114
|
|
|
|
|
292
|
push @temp,[$hunk]; |
216
|
|
|
|
|
|
|
} |
217
|
|
|
|
|
|
|
elsif (($path->[-1][0] < $hunk->[0]) && ($path->[-1][1] < $hunk->[1])) { |
218
|
390
|
|
|
|
|
1031
|
push @temp,[@$path,$hunk]; |
219
|
|
|
|
|
|
|
} |
220
|
|
|
|
|
|
|
} |
221
|
|
|
|
|
|
|
} |
222
|
309
|
|
|
|
|
577
|
@$R = @temp; |
223
|
309
|
|
|
|
|
577
|
$rank++; |
224
|
|
|
|
|
|
|
} |
225
|
72
|
|
|
|
|
1327
|
return $R; |
226
|
|
|
|
|
|
|
} |
227
|
|
|
|
|
|
|
|
228
|
|
|
|
|
|
|
# get all LCS of two arrays |
229
|
|
|
|
|
|
|
# records the matches by rank |
230
|
|
|
|
|
|
|
sub allLCS { |
231
|
72
|
|
|
72
|
1
|
305
|
my ($self,$X,$Y) = @_; |
232
|
|
|
|
|
|
|
|
233
|
72
|
|
|
|
|
103
|
my $m = scalar @$X; |
234
|
72
|
|
|
|
|
87
|
my $n = scalar @$Y; |
235
|
|
|
|
|
|
|
|
236
|
72
|
|
|
|
|
102
|
my $ranks = {}; # e.g. '4' => [[3,6],[4,5]] |
237
|
72
|
|
|
|
|
89
|
my $c = []; |
238
|
72
|
|
|
|
|
69
|
my ($i,$j); |
239
|
|
|
|
|
|
|
|
240
|
72
|
|
|
|
|
160
|
for (0..$m) {$c->[$_][0]=0;} |
|
549
|
|
|
|
|
723
|
|
241
|
72
|
|
|
|
|
135
|
for (0..$n) {$c->[0][$_]=0;} |
|
489
|
|
|
|
|
615
|
|
242
|
72
|
|
|
|
|
201
|
for ($i=1;$i<=$m;$i++) { |
243
|
477
|
|
|
|
|
707
|
for ($j=1;$j<=$n;$j++) { |
244
|
8952
|
100
|
|
|
|
10716
|
if ($X->[$i-1] eq $Y->[$j-1]) { |
245
|
438
|
|
|
|
|
709
|
$c->[$i][$j] = $c->[$i-1][$j-1]+1; |
246
|
438
|
|
|
|
|
345
|
push @{$ranks->{$c->[$i][$j]}},[$i-1,$j-1]; |
|
438
|
|
|
|
|
1759
|
|
247
|
|
|
|
|
|
|
} |
248
|
|
|
|
|
|
|
else { |
249
|
8514
|
100
|
|
|
|
23202
|
$c->[$i][$j] = |
250
|
|
|
|
|
|
|
($c->[$i][$j-1] > $c->[$i-1][$j]) |
251
|
|
|
|
|
|
|
? $c->[$i][$j-1] |
252
|
|
|
|
|
|
|
: $c->[$i-1][$j]; |
253
|
|
|
|
|
|
|
} |
254
|
|
|
|
|
|
|
} |
255
|
|
|
|
|
|
|
} |
256
|
72
|
|
|
|
|
165
|
my $max = scalar keys %$ranks; |
257
|
72
|
|
|
|
|
222
|
return $self->_all_lcs($ranks,1,$max); |
258
|
|
|
|
|
|
|
} |
259
|
|
|
|
|
|
|
|
260
|
|
|
|
|
|
|
1; |
261
|
|
|
|
|
|
|
__END__ |