[Purdue-pm] Perl Challenge 018

Ward, Mark Daniel mdw at purdue.edu
Sun Jul 28 20:54:28 PDT 2019

```Dear Mark,

#1 to use a brute force solution.  If you touch all substrings for a
word, then you will take a length of time that is exponential in the
length of the word.  In contrast, however, there is actually a solution
that is linear in terms of the length of the words.

https://en.wikipedia.org/wiki/Longest_common_substring_problem

The suffix tree solution -- which yields this optimal solution -- is
really beautiful in its own right, and it doesn't need to be a bunch of
complicated code.  It can be done easily, especially if you have a
library with a suffix tree included.  I don't think this is
over-engineering.  I think it gets to the heart of the solution.

So I find it hard to get excited about your suggestion to "put all
substrings for word[i] in set[i]" because this will take an exponential
number of steps, in terms of the length of the word, and that is
entirely inefficient.

Am I saying something stupid?  Maybe!  That is the danger of writing an
email late at night.  Well, it's only 10 PM here (not midnight) since
I'm in Denver at the moment, but that is still relatively late for me.

Warmest regards,

Mark

On 7/28/19 11:33 PM, Mark Senn wrote:
> My blog about Perl Weekly Challenge - 018 is at
>      https://engineering.purdue.edu/~mark/pwc-018.pdf
>
> It contains the two task descriptions and my Perl 6 (Perl 5 completely
> redesigned and rewritten from the ground up, even code as simple as
> \$array[1] = 1 doesn't work now---but it is worth it---Perl 6 is a
> much better language) code to solve the problems.
>
> I quote Jeff Atwood's "The Best Code is No Code At All" and Randall
> Munroe's xkcd comic strip because many of the solutions to the
> challenges are way over-engineered.
>
> Task #1: print the longest common substring in two or more substrings.
> Answer highlights: Put all substrings for word[i] in set[i] and use
> Perl 6's set intersection hyperoperator to find the longest substring.
>
> methods I had to write.  Just two parallel arrays.
>
> First get it working and if needed, then make it better.  And because
> the specs for the problems don't give any info about space or time
> constraints there is no need to make it better.
>
> -mark
> _______________________________________________
> Purdue-pm mailing list
> Purdue-pm at pm.org
> https://mail.pm.org/mailman/listinfo/purdue-pm
```