Re: Re: finding longest common substring

[sauoq]

While significantly faster than the OP's, I believe it suffers from some of the same scalability issues. That's one thing I hate about regular expressions: determining the complexity of an algorithm built on them tends to be very difficult.

Anyway, that also suffers from another problem. Try it with

my @a = ('a' . 'X' x 32768, 'a' . 'O' x 32768);

and you'll get an error:

Quantifier in {,} bigger than 32766 in regex; marked by <-- HERE in m/
+(.{ <-- HERE 32767}).*\0.*\1/

[revdiablo]

While significantly faster than the OP's

Actually, simply using index instead of m// in the grep makes my algorithm a bit faster than BrowserUk's regex. Granted, there's still a scalability problem here, but with the small tweak suggested by CombatSquirrel, it's much faster than the original, and works fine on data that is representative of what I'm actually using this for.

Here is the benchmark code I used:

Read more... (2 kB)

And here are the results I got:

Read more... (842 Bytes)

[BrowserUk]

I guess a length limit of 32k for the longest common substring could be a concern for some applications -- but nothing I regularly have to deal with.

Do you have an alternative?

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!
Wanted!