Функция Diff на двух массивах, в 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

Хотя обычно это делается с помощью букв, а не целых чисел, обычный алгоритм для вычисления расстояния Левенштейна должен работать здесь так же хорошо, как и там, где он обычно применяется.

Answer 2

Вам нужен алгоритм сопоставления строк, обычно реализуемый с помощью динамического программирования (см. здесь ).

Я бы настоятельно рекомендовал использовать библиотеку, которая выполняет diff вместо его реализации.сами.

Answer 3

Я разработчик библиотеки diff с C ++.

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

Используя мою библиотеку diff, можно рассчитать разницу между двумя последовательностями.

Пожалуйстасм. examples / intdiff.cpp о том, как использовать.