I wanted to polish my C++ and STL knowledge, so I thought it would be more interesting to adapt the diff algorithm directly to the list of insets -- longest common subsequence just sounds like a good algorithm for iterators, doesn't it?
You want to go for the difference algorithm based on the edit distance measure. It is better suited for this. See this link, which also explains the relation to LCS:
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/
The advantage would be that I don't need to detect mathmode changes etc. from the LyX or LaTeX file. Also I could recurse into the inset hierarchy and maybe detect changes within tables etc.
But to be really correct, you want to go for a tree difference algorithm rather than a linear one. Those can be complex, but there is a short-cut, which might be used in 1.5 when we have an XML format: xydiff:
http://www-rocq.inria.fr/gemo/XyDiff/
Regards, Asger
