#include <stdio.h>
#include "memory.h"
#define MAX_N 10000
typedef struct buff{
char data[10];
int size;
}buff;
buff p[MAX_N] = { 0, };
buff p_t[MAX_N] = { 0, };
//char p[MAX_N][10] = { 0, };
//char p_t[MAX_N][10] = { 0, };
unsigned long long hash[10][MAX_N] = { 0, }; // hash[n][0] is count.
unsigned long long mpow[10] = { 0, };
void merge_sort(int l, int r)
{
if (r - l < 1)
return;
int mid;
mid = (r + l) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int idx, ll, lr;
idx = ll = l;
lr = mid + 1;
for (int i = l; i <= r; i++)
{
memcpy(p_t[i].data, p[i].data, sizeof(p[i].data));
p_t[i].size = p[i].size;
}
while (ll <= mid && lr <= r)
{
if (p_t[ll].size <= p_t[lr].size)
{
memcpy(p[idx].data, p_t[ll].data, sizeof(p_t[ll].data));
p[idx++].size = p_t[ll++].size;
}
else
{
memcpy(p[idx].data, p_t[lr].data, sizeof(p_t[lr].data));
p[idx++].size = p_t[lr++].size;
}
}
while (ll <= mid)
{
memcpy(p[idx].data, p_t[ll].data, sizeof(p_t[ll].data));
p[idx++].size = p_t[ll++].size;
}
while (lr <= r)
{
memcpy(p[idx].data, p_t[lr].data, sizeof(p_t[lr].data));
p[idx++].size = p_t[lr++].size;
}
}
//length check
#if 0
int a = 12345;
int size = 0;
for (int i = 0; i < 10; i++)
{
size++;
a = a / 10;
if (a == 0) break;
}
#endif
int my_size_check(char * value)
{
int size = 0;
for (int i = 0; i < 10; i++)
{
if (value[i] != '\0')
size++;
else
break;
}
return size;
}
//calc hash table
unsigned long long my_pow(int x, int y)
{
unsigned long long result = 1;
for (int i = 0; i < y; i++)
{
result = result * x;
}
return result;
}
//1 * 275 + 2 * 275 * 275 + 3 * 275 * 275*275 + 4*275*275*275*275
//for test
#if 0
int a = 12345;
int b = 0;
for (int i = 4; i >= 0; i--)
{
b = a / my_pow(10, i);
a = a % my_pow(10, i);
}
#endif
#define HASH_DATA 257
unsigned long long current_hash[10] = { 0, };
void my_hash(char * x, int size)
{
unsigned long long hash_result = 0;
memset(current_hash, 0, sizeof(current_hash));
for (int i = 0; i < size; i++)
{
//hash_result = hash_result + (x[i]-'0') * my_pow(HASH_DATA, count++);
if (i == 0)
current_hash[i] = (x[i] - '0') * mpow[i];
else
current_hash[i] = current_hash[i-1] + (x[i] - '0') * mpow[i];
}
return;
}
int main(void)
{
int test_case = 0;
scanf("%d", &test_case);
for (int x = 0; x < 10; x++)
mpow[x] = my_pow(HASH_DATA, x);
for (int t = 0; t < test_case; t++)
{
int n = 0;
int size_pi = 0;
unsigned long long c_hash = 0;
int status = 0;
scanf("%d", &n); // max 10000
memset(p, 0, sizeof(p));
memset(p_t, 0, sizeof(p_t));
memset(hash, 0, sizeof(hash));
for (int nn = 0; nn < n; nn++)
{
scanf("%s", &p[nn].data);
p[nn].size = my_size_check(p[nn].data);
}
//merge sort for lenght
merge_sort(0, n-1);
// length 별로 해시 저장?
for (int i = 0; i < n; i++)
{
//1st. check size
size_pi = p[i].size;
//2nd. hash table size 작은것 부터 비교.
// 동일하게 시작부터 연속된 번호가 있는지 확인한다.
my_hash(p[i].data, p[i].size);
for (int k = 0; k < 10; k++)
{
if (hash[k][0] != 0)
{
//c_hash = my_hash(p[i].data, k + 1, size_pi);
for (int kk = 1; kk <= hash[k][0]; kk++)
{
if (current_hash[k] == hash[k][kk])
{
status = 1;
goto END;
}
}
}
}
//3rd. size 끝날때에 hash table save.
//c_hash = my_hash(p[i].data, size_pi);
hash[size_pi - 1][0] = hash[size_pi - 1][0]++;
hash[size_pi - 1][hash[size_pi - 1][0]] = current_hash[size_pi-1];
//long long hash[10][MAX_N+4] = { 0, }; // hash[n][0] is count.
}
END:
if (status == 0)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
최근 덧글