#!/usr/bin/perl
use strict;
use warnings;
use constant PATH  => 0;
use constant DEPTH => 1;

my @str = map {chomp; $_} <DATA>;
print LCS(@str), "\n";

# Longest Common Subsequence in strings
# Change required for duplicate chars
sub LCS{
    my @str = @_;

    # Map the position of each char in each string

    my @pos;
    for my $i (0 .. $#str) {
        my $line = $str[$i];
        for (0 .. length($line) - 1) {
            my $letter = substr($line, $_, 1);
            $pos[$i]{$letter} = $_;
        }
    }

    # Use 1 line as ref to map pos of same char in all lines
    # If lines are variable length, use smallest as ref
    # Establish lookup table also 

    my (%lookup, @order);
    for my $letter (split //, $str[0]) {
        my $char_map = [ map { $pos[$_]{$letter} } 0 .. $#pos ];
        $lookup{$char_map} = $letter;
        push @order, $char_map;        
    }

    # Predetermine which char mappings are greater than others

    my %greater;
    for my $i (0 .. $#order) {
        for my $j (grep $_ != $i, 0 .. $#order) {
            push @{$greater{$order[$i]}}, "$order[$j]" if is_greater(@order[$i, $j]);
        }
    }

    # A max depth watermark and a path representing that depth
    my ($max, $path) = (0, '');

    # Work queue of only char maps with char maps greater then it
    my @work = map [$_, 1], grep @{$greater{$_}}, keys %greater;

    while (@work) {
        my $item = pop @work;
        ($max, $path) = ($item->[DEPTH], $item->[PATH]) if $item->[DEPTH] > $max;
        my $last_node = (split /:/, $item->[PATH])[-1];
        next if ! exists $greater{$last_node};
        my @next_node = @{ $greater{$last_node} };
        push @work, map ["$item->[PATH]:$_", $item->[DEPTH] + 1], @next_node;
    }

    my $hidden_msg = join '', map $lookup{$_}, split /:/, $path;
    return $hidden_msg;
}

# Are all vals in ref2 greater than corresponding vals in ref1
sub is_greater {
    my ($ref1, $ref2) = @_;
 
    # Stop at end of smallest ref
    my $end = $#$ref1 > $#$ref2 ? $#$ref2 : $#$ref1;

    for (0 .. $end) {
        return 0 if $ref2->[$_] <= $ref1->[$_];
    }
    return 1;
}