使用最小表示法进行比较Hash值相同的雪花

最小表示法返回正向与逆向中总的最小表示

C++ 代码

/**
 * 1. Hash
 * 2. 最小表示法
 */
#include <bits/stdc++.h>

using namespace std;
const int maxn = 100010;
int n;
int snow[maxn][6];
int Next[maxn], head[maxn], tot;
int s1[15], s2[15];
const int mod = 99991;

// 求正向和逆向总的最小表示，将最小表示存入ans中
void getMin(int now[], int ans[]){
    // 正向逆向复制一遍
    for(int i = 0; i < 12; ++ i)
        i < 6 ? s1[i] = now[i] : s1[i] = now[i - 6];
    for(int i = 11, k = 0; k < 12; -- i, ++ k)
        k < 6 ? s2[i] = now[k] : s2[i] = now[k - 6];

    //求正向的最小表示
    int i = 0, j = 1, k = 0;
    while(i < 6 && j < 6){
        for(k = 0; k < 6 && s1[i + k] == s1[j + k]; ++ k);
        if(k == 6) break;
        if(s1[i + k] < s1[j + k]){
            j = j + k + 1;
            if(j == i) j ++;
        }else if(s1[i + k] > s1[j + k]){
            i = i + k + 1;
            if(i == j) i ++;
        }
    }
    int pos1 = min(i, j);

    //求逆向的最小表示
    i = 0, j = 1, k = 0;
    while(i < 6 && j < 6){
        for(k = 0; k < 6 && s2[i + k] == s2[j + k]; ++ k) ;
        if(k == 6) break;
        if(s2[i + k] < s2[j + k]){
            j = j + k + 1;
            if(j == i) j ++;
        }else if(s2[i + k] > s2[j + k]){
            i = i + k + 1;
            if(i == j) i ++;
        }
    }
    int pos2 = min(i , j);

    //求正向、逆向中较小的一个
    int flag = 0;
    for(int i = pos1, j = pos2, k = 0; k < 6; i ++, j ++ , k ++){
        if(s1[i] == s2[j]) continue;
        else if(s1[i] < s2[j]){
            flag = 1;
            break;
        }else{
            flag = 2;
            break;
        }
    }
    //最小表示赋值给ans
    for(int i = 0; i < 6; ++ i)
        flag == 1 ? ans[i] = s1[i + pos1] : ans[i] = s2[i + pos2];
}

int getHash(int now[]){
    int ans = 1;
    for(int i = 0; i < 6; ++ i) ans = 1ll * ans * now[i] % mod;
    for(int i = 0; i < 6; ++ i) ans = (1ll * ans + now[i]) % mod;
    return ans % mod;
}

//若加入时有一样的雪花则返回1，否则返回0
bool add(int now[]){
    int val = getHash(now); //获取Hash值
    int ans1[10], ans2[10];
    for(int i = head[val]; i; i = Next[i]){ //遍历相同hash值的链表
        //1. 获取两个相同hash值的雪花的正逆最小表示
        getMin(snow[i], ans1);
        getMin(now, ans2);
        //2. 判断是否相等
        bool flag = 0;
        for(int i = 0; i < 6; ++ i)
            if(ans1[i] != ans2[i]) flag = 1;
        if(flag) continue;
        else return 1;
    }

    // 不相等则加入到链表中
    tot ++;
    for(int i = 0; i < 6; ++ i)
        snow[tot][i] = now[i];
    Next[tot] = head[val], head[val] = tot;
    return 0;
}

int main(){
    int tmp[10];
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i){
        for(int j = 0; j < 6; ++ j) scanf("%d", &tmp[j]);
        if(add(tmp)){
            printf("Twin snowflakes found.");
            return 0;
        }
    }
    printf("No two snowflakes are alike.");
    return 0;
}