整数シーケンスのC++の効果的な比較（相対的な順序で）

Question

C++で比較アルゴリズムを効果的に実装していただきありがとうございます。 私のプログラムは整数列の行からなる入力を受け取り、どのシーケンスが重複しているかを調べる必要があります。しかし、いくつかのシーケンスは横にシフトするかもしれません、そして、それはまだ等しい必要があります。 これは、例えばシーケンス{0,1,2、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マッピングのハッシュコードを作成することができます。