Найти совпадения 2 массивов

[Igors]

Добрый день

Задача очень близка к сравнению 2-х текстовых файлов.  Есть 2 массива (вектора) A и B строк (или др. объектов для которых определен оператор ==). Найти массив С максимального размера, элементы которого есть пары индексов в исходных A и B, напр

Код

C++ (Qt)
// элемент выходного массива C 
struct CIndex {
  int mIndex1;   // индекс строки в A
  int mIndex2;   // индекс (той же) строки в B
};

Обязательное условие: оба индекса в C строго упорядочены, т.е.

Код

C++ (Qt)
// для любого i
C[i].mIndex1 < C[i + 1].mIndex1 
C[i].mIndex2 < C[i + 1].mIndex2
 

Спасибо

[JayFOX]

Стало интересно, а если искомый массив нельзя определить однозначно? Например:
A: 1 2 3 4
B: 4 3 2 1

Все совпадения:
(1, 4)
(2, 3)
(3, 2)
(4, 1)
Тут массивов максимальной длины - 4, так как не выполняется ни для одного

Обязательное условие: оба индекса в C строго упорядочены
 

[Igors]

Там легко, получилось в тот же день. Псевдокод

Код

C++ (Qt)
int indexA = 0;  // "текущий" индекс в массиве A
int indexB = 0;  // "текущий" индекс в массиве B
 
// цикл сравнения
while (indexA < A.size() && indexB < B.size()) {
 
// совпадение
 if (A[indexA] == B[indexB])  {
  C.push_back(std::make_pair(indexA, indexB));
  ++indexA;
  ++indexB;
  continue;
 }
 
// находим первую совпадающую строку в B  
 size_t pos = Lookup(B, indexB + 1, B.size(), A[indexA]);
 
// если такой нет, переходим к следующей в A
 if (pos >= B.size()) {
  ++indexA;
  continue;
 }
 
// сколько строк мы "упустили"
 size_t numSkip = pos - indexB;
 
// пытаемся найти вариант с меньшим числом "упущенных" строк
 for (size_t i = indexA + 1; i < std::min(indexA + numSkip, A.size()); ++i) {
  size_t numSkip2 = i - undexA + Lookup(B, indexB, std::min(indexB + numSkip, B.size()); A[i]);
  if (numSkip2 < numSkip) {
   // и.т.д. подробности очевидны
 } 
}