blob: 21a698fb191c0bebc0ec56a8fc2e603b338fba58 (
plain) (
tree)
|
|
#!/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;
|