Then, I go through the words one by one. For each word, I try all the positions and all possible lengths of its subwords (and I skip the maximal length at position 0, because that would breake the rule #2). For each subword, I do nothing if it has already been printed out (each word should be reported just once). I do nothing if rules #3 or #4 apply. Otherwise, I check whether the subword is itself on the list of words. If it is, I report it and book it as such. And that's it.

The basic idea was this: Comparing each word to all other words would take ages. There would be many comparisons of words that are totally incompatible. How can I reduce the number of comparisons? I do not need all the words, I only need those that are possible for the given word.

As I read the code know, I think it might be optimized a bit further. Instead of caching the reported subwords, you can cache the tested ones (i.e. move the undef three lines up, before the "if"). %reported should be renamed to %checked then.

Got it!

The only piece in the code I am wondering about is where you are checking for rules 3 and 4 and use "$subword . q{s}..."

I know what it is doing but where did the "q" come from?

Thank you!

http://perldoc.perl.org/perlop.html#Quote-and-Quote-like-Operators

Customary  Generic        Meaning        Interpolates
    ''       q{}          Literal             no
    ""      qq{}          Literal             yes
    ``      qx{}          Command             yes*
            qw{}         Word list            no
    //       m{}       Pattern match          yes*
            qr{}          Pattern             yes*
             s{}{}      Substitution          yes*
            tr{}{}    Transliteration         no (but see below)
             y{}{}    Transliteration         no (but see below)
    <<EOF                 here-doc            yes*

    * unless the delimiter is ''.
[download]