#!/usr/bin/perl

use warnings;
use strict;

my %dictionary;
open(my $dict_file, '<', '2of12inf.txt') or die ("Can't open dictionary: $!");
while (<$dict_file>) {
        $_ = lc($_);
        tr/a-z//dc;
        $dictionary{$_} = 1;
}

my @partials;
while (<DATA>) {
        $_ = lc($_);
        tr/a-z//dc;
        @partials = (); $partials[0] = [''];
        my $results = wordify($_);
        print "$_:\n";
        print "$_\n" for @$results;
}

sub wordify {
        my ($string) = @_;
        my $results = [];
        my $min_end = length($string);
        for (my $pos = 0; $pos < $min_end; $pos++) {
                for my $len (1 .. length($string) - $pos) {
                        my $word = substr($string, $pos, $len);
                        if (exists $dictionary{$word}) {
                                $min_end = $pos+$len if $pos+$len < $min_end;
                                my $prefix = '';
                                $prefix = '[' . substr($string, 0, $pos) . '] ' unless $pos == 0;
                                $prefix .= $word;
                                my $rest = substr($string, $pos + $len);
                                wordify($rest) unless (defined $partials[length($rest)]);
                                my $endings = $partials[length($rest)];
                                push(@$results, map("$prefix $_", @$endings));
                        }
                }
        }
        $results = ["[$string]"] unless @$results;
        $partials[length($string)] = $results;
        return $results;
}

__DATA__
penisland
zatxtaz
xapenx