perlquestion
rkg
Hi -- <p>
I've been using <a href=
"http://search.cpan.org/author/DYACOB/String-LCSS-0.12/lib/String/LCSS.pm"> String-LCSS </a> and it is sloooooow on long inputs. <P>
I haven't studied the algorithm or the implementation, but just using it suggests it is O(n^2) or worse.<p>
Is this just the nature of the LCSS problem, or is there a better implementation around? <p>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? <p> I'm not looking to write a generalized heurisitic around this (tabu or simulated annealing or whatever) at this point.
<p>
Thanks
<p>
[rkg]
<p>
P.S. I brought this up on Perlmonks <a href="http://perlmonks.com/index.pl?node_id=249239">before</a>,
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?)