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

Question

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

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

Answer 1

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

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 отображение хэш-код для отображения индексов в последовательности, так что вам нужно сделать полную проверку, только если хэш то же самое.