All,
The other day blokhead told me about an interesting pairing on the Women's Tennis World Tour. Consider the following 3 players. Specifically, there last names and the relationship between prefix and suffix matching. 
Caroline Wozniacki
Aleksandra Wozniak
Sabine Lisicki

prefix(Wozniacki, Wozniak) = Woznia
suffix(Wozniacki, Lisicki) = cki

Woznia . cki = Wozniacki

[download]

He wondered if any other such pairings existed and if there were an elegant solution to the general problem. This interested me so I asked a few clarifying questions to establish some rules:

I came up with the following solution using a dictionary and not tennis players. 

#!/usr/bin/perl
use strict;
use warnings;
use Storable;

my ($prefix_db, $suffix_db, $dict_db) = (qw/prefix.db suffix.db dict.d
+b/);

if (! -e $prefix_db || ! -e $suffix_db || ! -e $dict_db) {
    my (%prefix, %suffix, %dict);
    open(my $fh, '<', 'words.txt') or die "Unable to open 'words.txt' 
+for reading: $!";
    while (<$fh>) {
        tr/a-z//cd;
        next if length($_) < 2;
        build_tree(\%prefix, \%suffix, $_);
        $dict{$_} = undef;
    }
    store(\%prefix, $prefix_db);
    store(\%suffix, $suffix_db);
    store(\%dict,   $dict_db);
}
my ($prefix, $suffix, $dict) = (retrieve($prefix_db), retrieve($suffix
+_db), retrieve($dict_db));

my $req = $ARGV[0] or die "Usage: $0 <word>";
die "'$req' is not in dictionary" if ! exists $dict->{$req};

for my $idx (0 .. length($req) - 2) {
    my $pre  = substr($req, 0, $idx + 1);
    my $char = substr($req, $idx, 1);
    my $next = substr($req, $idx + 1, 1);
    my @head = map { $prefix->{$pre}{'*words*'}{$_} ne $next ? $_ : ()
+ } keys %{$prefix->{$pre}{'*words*'}};
    next if ! @head;  # Should this be last instead?
    my $suf  = substr($req, $idx + 1);
    my @tail = map { $suffix->{$suf}{'*words*'}{$_} ne $char ? $_ : ()
+ } keys %{$suffix->{$suf}{'*words*'}};
    next if ! @tail;  # Should this be last instead?
    # Cartesian Product Possible
    print "prefixmatch($req, $head[0]) = $pre, suffixmatch($req, $tail
+[0]) = $suf, $pre . $suf = $req\n";
}

sub build_tree {
    my ($prefix, $suffix, $word) = @_;

    # Prefix hello => h, he, hel, hell but not hello
    for my $idx (0 .. length($word) - 2) {
        my $pre = substr($word, 0, $idx + 1);
        $prefix->{$pre}{'*words*'}{$word} = substr($word, $idx + 1, 1)
+;
    }

    # Suffix hello => o, lo, llo, ello but not hello
    for my $idx (1 .. length($word) - 1) {
        my $suf = substr($word, $idx);
        $suffix->{$suf}{'*words*'}{$word} = substr($word, $idx - 1, 1)
+;
    }
}
__END_
$ ./match_me.pl hello

prefixmatch(hello, haughtiness) = h, suffixmatch(hello, bordello) = el
+lo, h . ello = hello
prefixmatch(hello, hepatic) = he, suffixmatch(hello, armadillo) = llo,
+ he . llo = hello
prefixmatch(hello, helical) = hel, suffixmatch(hello, gigolo) = lo, he
+l . lo = hello
prefixmatch(hello, hellhole) = hell, suffixmatch(hello, kangaroo) = o,
+ hell . o = hello

# Note:  Not all possible matches, just one of each prefix length

[download]

This has a heavy penalty the first time it is ran but is relatively fast after. Can you do better?

Cheers - L~R

In reply to Challenge: prefix($x, $y) . suffix($x, $z) eq $x by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.