Re: suffix arrays

[jonadab]

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.