Russian Qt Forum
Ноябрь 11, 2024, 01:14 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: Найти совпадения 2 массивов  (Прочитано 4187 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Июнь 13, 2011, 14:51 »

Добрый день

Задача очень близка к сравнению 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
Гость
« Ответ #1 : Июль 01, 2011, 17:23 »

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

Все совпадения:
(1, 4)
(2, 3)
(3, 2)
(4, 1)
Тут массивов максимальной длины - 4, так как не выполняется ни для одного
Цитировать
Обязательное условие: оба индекса в C строго упорядочены
 
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Июль 01, 2011, 18:39 »

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

Код
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) {
  // и.т.д. подробности очевидны
}
}
 
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.102 секунд. Запросов: 22.