diff options
-rw-r--r-- | LREP.pl | 56 |
1 files changed, 56 insertions, 0 deletions
@@ -0,0 +1,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; |