Re: minimal superstrings/maximal substrings

[tybalt89]

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