字符串哈希 + 字符串最小表示法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <cmath>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 3,null = 0x3f3f3f3f, P = 131;
unordered_set<unsigned long long>st;
int s[20];
int n = 6,m;
ULL h[10];
ULL g[10];
int f(){
for(int i = 1; i <= n; i ++) s[n + i] = s[i];
int i = 1,j = 2, k;
while(i <= n && j <= n){
for(k = 0; k < n && s[i + k] == s[j + k]; k ++);
if(k == n)break;
if(s[i + k] > s[j + k]){
i = i + k + 1;
if(i == j) i ++;
}else{
j = j + k + 1;
if(i == j) j ++;
}
}
return min(i,j);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
memset(h,0x3f,sizeof h);
cin >> m;
bool flag = false;
for(int i = 0; i < m ; i ++){
g[0] = 0;
h[0] = 0;
for(int i = 1; i <= 6; i ++){
cin >> s[i];
}
int x = f();
int t = 1;
for(int j = 0; j < 6; j ++, t ++){
h[t] = s[x + j] + P * h[t - 1]; //右旋
int idx = x - j >= 1 ? x - j : x + 6 - j; //左旋
g[t] = g[t - 1] * P + s[idx];
}
if(st.count(g[6]) || st.count(h[6])){
flag = true;
break;
}
else {
st.insert(g[6]);
st.insert(h[6]);
}
if(flag)
break;
}
if(flag)
cout << "Twin snowflakes found." << endl;
else
cout << "No two snowflakes are alike." << endl;
}