From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2002-10-22 02:44:49
"Bohdan" <warever_at_[hidden]> wrote in message
> Thanks for links.
> I don't think that using matrix for string comparison is a good idea.
> Memory for matrix should be allocated dynamically, this doesn't allow
> to implement fast algorithm. Besides all it has O(n*n) speed and doesn't
> for two sequence difference ( parameters: 2 pairs of forward iterators ).
Fear not ! My implementation uses linear memory, not a full matrix like
that described in the article. If you're interested, take a look at the
longest_common_subsequence_length() algorithm in the sand-box at
The fundamental algo is the same, and just the core of the loop changes for
> I think that lavenstain difference should be in boost, but it is not
There are always alternatives to every algorithm, often suitable for
different datasets. Sure, we should not just have a single implementation to
try to cover all uses.
> More interesting is some kind algorithm with some limitations and better
> perfomance. I'm not ready for more detailed conversation yet. i'll read
> about various edit-differences when i have more time and i hope to propose
> alternative ways.
> But maybe your implementaion alredy doesn't use dynamic memory and is
> Than i'm wasting time :)
It's never a waste of time to discuss implementation details of algorithms,
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk