I took a shot at doing this, based on the DDJ code

This will generally not work very well. You asked for wisdom, so here is some: Perl is not C. What is fast in C may be slow in Perl, and vice versa, but even more importantly, many "algorithms" designed for C are designed to take detailed control over minutia. In many cases they are not so much algorithms as implementations, or perhaps (as in this case) something of each.

I generally have misgivings when I see people trying to do line-for-line, function-for-function adaptations from C to Perl. It's fundamentally a wrong approach for anything more complex than Hello World.

I have even stronger misgivings about taking code that uses pointers in C and adapting it to use references in Perl. While it's true that Perl's references are conceptually analogous to C's pointers, it is NOT true that what is done with pointers in C should usually be done with references in Perl. Occasionally, yes, but not usually and certainly not always -- and probably not in this case. A lot of the things that are done in C with pointers are fiddly low-level details that in Perl are best left to the optimizer to sort out. Once you start down the path of trying to do a line-for-line translation, you will end up using hashes for structs, using references for pointers, implementing a linked-list structure with a $member{next} reference in each anonymous hash, instead of just using a list for crying out loud. This is an extreme example, but it demonstrates the point: structure-for-structure translations from C to Perl can be very suboptimal, both in terms of performance and programmer time.

All of that is to say, perhaps you would get further by asking what is the best or fastest way to find the longest repeated substrings of a string in Perl. I personally don't know the answer to this question, but someone on Perlmonks might, and you're more likely to get a satisfactory answer to that one than the question that you posted, IMO.

Quidquid latine dictum sit altum viditur.

In reply to Re: suffix arrays by jonadab
in thread suffix arrays by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.