[РЕШЕНО] Поиск изменений между массивами

[Racheengel]

Может, конечно, это я туплю, но такая вроде бы простая задача "не гуглится".
В общем - есть 2 массива, второй является производным от первого, но в несколько изменённом состоянии (где-то что-то удалили, где-то добавили, где-то заменили и пр.) Задача - найти "где" и "что".
Решение "в лоб", в принципе, я сделал, но не верю, что нет ничего стандартного...

[Igors]

Неск лет назад это делал, спрашивал здесь же (рез-т тот же). Очень близко к "сравнению исходников". Долго разрывать, что (смутно) помню: сначала оба массива поделить на "блоки", псевдокод

Код

C++ (Qt)
struct Block {
 int beg, end;  // первый и последний эл-ты
 int match;   // индекс блока с тем же содержимым для 2-го массива (или -1 если такого нет)
};
 

После этого все сразу "ложится"

[Old]

Решение "в лоб", в принципе, я сделал, но не верю, что нет ничего стандартного...

Ну прямо стандартного конечно нет, но если речь про бинарный diff, то библиотек есть не мало.
Например, вот: https://github.com/cubicdaiya/dtl

[Igors]

Пусть есть массивы/контейнеры A и B и текущие позиции i для A и j для B. Тогда

- если A[ i ] == B[ j ] то наращиваем совпадающий блок до упора

- иначе ищем первое совпадение в противоположном массиве (в B для A[ i ] и в А для B[ j ]). Напр оказалось A[ i ] == B[ j + 5 ]. Это значит мы нашли решение при котором не совпало 5 эл-тов. Пытаемся улучшить его повторив поиск для A[ i + 1 ]....A[ i + 4 ]. Напр если A[ i + 1 ] == B[ j ], то всего 1 эл-т не совпал. Ну дальше "дело техники" оформить это рекурсией

[rudireg]

Может так?

Код

C++ (Qt)
A[100]; //исходные данные
B[100];
 
for(int i=0; i<100; ++i){
    if( A[i] != B[i] )
       //Нет совпадения
}
 

[Bepec]

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

[Racheengel]

Да, в принципе я примерно так и сделал - искал сначала совпадающий блок, потом параллельно просматривал оба массива до первого "значительного" совпадения (т.е. как минимум более 1 символа, это настраивается), потом генерировал элемент для SES и тд.

В общем, всем спасибо) Igors, Old: посмотрю еще "бинарный diff", возможно, он будет более шустрым, чем моё велосипедо.

[joker]

Я извиняюсь, что влажу, но постановка задачи очень сильно напомнила вот такую штуку
Может быть поможет.

https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0