Pathologically Eclectic Rubbish Lister | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
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. Thanks 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?) In reply to LCCS time complexity by rkg
|
|