Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: Challenge: prefix($x, $y) . suffix($x, $z) eq $x

by FunkyMonk (Chancellor)
on Apr 22, 2009 at 21:43 UTC ( [id://759420]=note: print w/replies, xml ) Need Help??


in reply to Challenge: prefix($x, $y) . suffix($x, $z) eq $x

/me joins in the fun

open my $DICT, "<", "players" or die $!; my (%words, %suffix, %prefix); while (defined(my $word = <$DICT>)) { chomp $word; $word = lc $word; next unless $word =~ m/^[a-z]{2,}$/; next if $words{$word}++; push @{$suffix{substr $word, $_}}, $word for (1 .. length($word) - 1); push @{$prefix{substr $word, 0, $_}}, $word for (1 .. length($word) - 1); } #find_words("wozniacki"); find_words("zhou"); find_words($_) for sort keys %words; sub find_words { my $word = shift; die "not a \"word\"" unless exists $words{$word}; for my $idx (1 .. length($word) - 1) { my $prefix = substr $word, 0, $idx; my $suffix = substr $word, $idx; next unless exists $prefix{$prefix} && exists $suffix{$suffix} +; my @pref_words = grep {$_ ne $word} @{$prefix{$prefix}}; my @suff_words = grep {$_ ne $word} @{$suffix{$suffix}}; next unless @pref_words && @suff_words; say $prefix, ".", $suffix; say " PREFIX $prefix: @pref_words"; say " SUFFIX $suffix: @suff_words"; } }

Sample output:

woznia.cki PREFIX woznia: wozniak SUFFIX cki: lisicki zh.ou PREFIX zh: zhang zhao zharkova zheng zhong SUFFIX ou: daniilidou fafaliou georgatou gerasimou zho.u PREFIX zho: zhong SUFFIX u: anghelescu begu buzarnescu cadantu daniilidou dulgheru faf +aliou georgatou gerasimou hincu hisamatsu hsu liu lu mitu nedelcu nic +ulescu olaru perianu qiu radu senoglu shimizu stancu tigu vaideanu xu + yu

and the full output eek. There's an awfull lot of it (>200K) for the full list of players

Timings (full run):

real 0m0.266s user 0m0.256s sys 0m0.012s

Replies are listed 'Best First'.
Re^2: Challenge: prefix($x, $y) . suffix($x, $z) eq $x
by Limbic~Region (Chancellor) on Apr 22, 2009 at 22:28 UTC
    FunkyMonk,
    I believe this code is flawed in that it violates two of the rules.
    • The maximum match must be taken.
    • Entire word can not be matched

    Changing the players for a dictionary file, I tried 'hello'. It produced the following:

    h.ello PREFIX h: ha haberdasher ..... he head
    Neither 'he' nor 'head' should be matched here because they share more than just 'h' in common with 'hello'. 'he' should be excluded because it consumes the entire word.

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://759420]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2024-03-19 07:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found