алгоритм — эффективное сравнение целочисленных последовательностей на языке C ++ (в относительном порядке)

Буду признателен за помощь в эффективной реализации алгоритма сравнения в C ++.
Моя программа получает входные данные, которые состоят из строк целочисленных последовательностей, и мне нужно найти, какие последовательности являются дубликатами. Но некоторые последовательности могут быть сдвинуты в сторону, и все равно должны быть равны.
Имея это в виду, например, последовательности {0, 1, 22, 5, 9} и {22, 5, 9, 0, 1} должны быть равны. Эти последовательности или количество повторяющихся последовательностей могут иметь размер.

Кажется, я не могу думать о чем-то, что в какой-то мере эффективно (сравнение каждой новой строки со всеми остальными занимает слишком много времени), поэтому я надеюсь, что кто-то может помочь. Заранее спасибо!

0

Решение

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

unsigned long long hash(const std::vector<int>& seq) {
unsigned long long result;
for (int i=0,n=seq.size(),j=n-1; i<n; j=i++) {
result ^= seq[i] * 69069ULL + seq[j];
}
return result;
}

Тогда вы можете создать std::map отображение хеш-кода в список индексов в последовательности, поэтому вам нужно выполнить полную проверку, только если хеш-код совпадает.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]