[정올 3137] 전화번호 검색

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2419&sca=99&sfl=wr_hit&stx=3137 

JUNGOL

#include <stdio.h>

int T, N;
char dial[10010][11];
int len[10010], trienum[11][11], bcnt; //'0'~'9' 그리고 10번째는 0(다음거 없는것)
bool num2digit[11][2]; //0번: 2자리수 이상이 있는지, 1번: 1자리수가 있는지
int strlen(char* s, int len = 0) {
	while (s[len]) len++;
	return len;
}
int strncmp(char* s, char* t, int n) {
	while (n > 1 && *s && *s == *t) ++s, ++t, --n;
	return *s - *t;
}
struct trie {
	int didx; //dial index
	trie* next;
	void init() {
		didx = 0; next = nullptr;
	}
	trie* alloc(int idx, trie* p) {
		didx = idx; next = p;
		return this;
	}
} buf[50000], *tab[11][11];
void init() {
	for (int i = 0; i < N; i++) {
		len[i] = 0; dial[i][0] = 0;
	}
	for (int i = 0; i < 11; i++) {
		num2digit[i][0] = num2digit[i][1] = false;
		for (int j = 0; j < 11; j++) {
			trienum[i][j] = 0;
			tab[i][j] = nullptr;
		}
	}
	for (int i = 0; i < bcnt; i++) buf[i].init();
	bcnt = 0;
}
inline int getidx(char c) {
	return (c == 0) ? 10 : c - '0';
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		init();
		scanf("%d", &N);
		bool find = false;
		for (int n = 0; n < N; n++) {
			scanf("%s", dial[n]);
			if (find) continue;
			const int idx1 = getidx(dial[n][0]);
			const int idx2 = getidx(dial[n][1]);
			trienum[idx1][idx2]++;
			len[n] = strlen(dial[n]);
			if (idx2 == 10) num2digit[idx1][1] = true;
			else num2digit[idx1][0] = true;
			if (num2digit[idx1][0] && num2digit[idx1][1]) { find = true; continue; } //1자리 수와 2자리수 둘 다 있다면
			tab[idx1][idx2] = buf[bcnt++].alloc(n, tab[idx1][idx2]);
			if (trienum[idx1][idx2] > 1) {
				for (trie* p = tab[idx1][idx2]; p; p = p->next) {
					if (p == nullptr) break;
					if (p->didx == n) continue;
					int minlen = (len[n] > len[p->didx]) ? len[p->didx] : len[n];
					if (strncmp(dial[n], dial[p->didx], minlen) == 0) { find = true; break; }
				}
			}
		}

		if (find) printf("NO\n");
		else printf("YES\n");
	}

	return 0;
}