1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#!/usr/bin/env perl
use strict;
use warnings;
use 5.016;
chomp(my $s = <>);
chomp(my $k = <>);
chomp(my @edges = <>);
my %nodes;
for my $edge (@edges) {
my ($node1, $node2, $begin, $length) = split ' ', $edge;
push @{ $nodes{$node1}{children} ||= [] }, $node2;
$nodes{$node2} = {
str => substr($s, $begin - 1, $length),
parent => $node1,
children => [],
};
}
my ($root) = grep { !exists $nodes{$_}{parent} } keys %nodes;
sub {
my ($node) = @_;
my $leaves = 0;
for my $child (@{ $nodes{$node}{children} }) {
$leaves++ if @{ $nodes{$child}{children} } == 0;
$leaves += __SUB__->($child);
}
$nodes{$node}{leaves} = $leaves;
return $leaves;
}->($root);
sub {
my ($node, $full_str) = @_;
$nodes{$node}{full_str} = $full_str;
for my $child (@{ $nodes{$node}{children} }) {
__SUB__->($child, $full_str . $nodes{$child}{str});
}
}->($root, '');
my $longest = '';
sub {
my ($node) = @_;
if ($nodes{$node}{leaves} >= $k) {
if (length($nodes{$node}{full_str}) > length($longest)) {
$longest = $nodes{$node}{full_str};
}
}
for my $child (@{ $nodes{$node}{children} }) {
__SUB__->($child);
}
}->($root, '');
say $longest;
|
