Там легко, получилось в тот же день. Псевдокод
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) {
// и.т.д. подробности очевидны
}
}