Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: minimal superstrings/maximal substrings

by tybalt89 (Parson)
on Aug 20, 2019 at 10:21 UTC ( #11104719=note: print w/replies, xml ) Need Help??


in reply to minimal superstrings/maximal substrings

Straight from the problem description. Probably O(N**3) or greater.

#!/usr/bin/perl # https://perlmonks.org/?node_id=11104709 use strict; use warnings; use List::Util qw( none ); use Path::Tiny; my @words = # get some wor +ds grep /^fun/, # for shorter +testing grep /^[a-z]+$/, path('/usr/share/dict/words')->lines({chomp => 1}); my @longs = grep length $_ >= 9, @words; # all legal lo +ng words for my $short ( grep length $_ <= 8, @words ) # all legal sh +ort words { for my $long ( grep /$short/, @longs ) # all long sup +erstrings { if( none { # test for wor +d between length $_ > length $short and length $_ < length $long and $long =~ $_} @words ) { print "$long $short\n"; } } }

Outputs:

funicular fun funniness fun functional function functionaries function functionary function functioned function functioning function functions function fundamental fund fundraiser fund fundraising fund funereally funereal fungicidal fungi fungicide fungi fungibles fungible funkiness funk funneling funnel

Replies are listed 'Best First'.
Re^2: minimal superstrings/maximal substrings
by tybalt89 (Parson) on Aug 20, 2019 at 10:45 UTC

    Or use regex to find if there is a word between.

    #!/usr/bin/perl # https://perlmonks.org/?node_id=11104709 use strict; use warnings; use List::Util qw( none ); use Path::Tiny; my @words = # get some wor +ds grep /^fun/, # for shorter +testing grep /^[a-z]+$/, path('/usr/share/dict/words')->lines({chomp => 1}); my @longs = grep length $_ >= 9, @words; # all legal lo +ng words my $string = join ' ', sort { length $a <=> length $b } @words; for my $short ( grep length $_ <= 8, @words ) # all legal sh +ort words { for my $long ( grep /$short/, @longs ) # all long sup +erstrings { if( $string !~ # test for wor +d between /\b$short\b.*?\b(\w*$short\w*)\b.*?\b(?=$long\b)\w*\1\w*\b/ ) { print "$long $short\n"; } } }

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (6)
As of 2019-09-18 09:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    The room is dark, and your next move is ...












    Results (227 votes). Check out past polls.

    Notices?