|Perl Monk, Perl Meditation|
LCCS time complexityby rkg (Hermit)
|on Sep 09, 2003 at 13:20 UTC||Need Help??|
rkg has asked for the
wisdom of the Perl Monks concerning the following question:
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?)