Diff function on two arrays, in c++/mfc/stl?

Question

Diff function on two arrays (or how to turn Old into New) 

Example
One[]={2,3,4,5,6,7}
Two[]={1,2,3,5,5,5,9}

Example Result
Diff: insert 1 into One[0], One[]={1,2,3,4,5,6,7}
Diff: delete 4 from One[3], One[]={1,2,3,5,6,7}
Diff: modify 6 into 5 in One[4], One[]={1,2,3,5,5,7}
Diff: modify 7 into 5 in One[5], One[]={1,2,3,5,5,5}
Diff: append 9 into One[6], One[]={1,2,3,5,5,5,9}

Need code in c++/mfc/stl/c, Thanks.

Answer 1

What you need is a string matching algorithm, usually implemented using dynamic programming (see here).

I'd highly suggest using a library that performs the diff instead of implementing it yourself.

Answer 2

Though it's normally done with letters instead of integers, the usual algorithm for computing the Levenstein distance should work just as well here as where it's usually applied.

Answer 3

Hi, I'm diff library developer with C++.

http://code.google.com/p/dtl-cpp/

Using My diff library, it is possible to calculate the difference between two sequences.

Please see examples/intdiff.cpp about how to use.