rkg has asked for the wisdom of the Perl Monks concerning the following question:

Hi --

I've been using String-LCSS and it is sloooooow on long inputs.

I haven't studied the algorithm or the implementation, but just using it suggests it is O(n^2) or worse.

Is this just the nature of the LCSS problem, or is there a better implementation around?

Are there any fast approximation algorithms for LCCS? That is, if I can settle for a pretty-long-but-not-necessarily-the-mathematically-longest common substring ("PLBNNTMLCSS" vs "LCCS"), are there good heuristics around?

I'm not looking to write a generalized heurisitic around this (tabu or simulated annealing or whatever) at this point.



P.S. I brought this up on Perlmonks before, but there's confusion between LCSS and LCS. Different problems. (At least I think they are. Maybe I am missing something and LCSS can be derived from LCS?)