another solution

1 files changed, 56 insertions, 0 deletions

diff --git a/LREP.pl b/LREP.pl
new file mode 100644
index 0000000..21a698f
--- /dev/null
+++ b/LREP.pl
@@ -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;