[정올 1885] 접두사

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

JUNGOL

#include <stdio.h>

const int LM = 1 << 20;
int strlen(char* s, int len = 0) {
	while (s[len]) len++;
	return len;
}
int strncmp(char* s, char* t, int n) { //s가 t보다 앞서면 음수, 같으면 0, t가 s보다 앞서면 양수
	while (n > 1 && *s && *s == *t) ++s, ++t, --n;
	return *s - *t;
}
int strcmp(const char* s, const char* t) {
	while (*s && *s == *t) s++, t++;
	return *s - *t;
}
int T, N, bcnt, wlen[10010], wcnt[11];
char word[10010][105];
struct data {
	char* str;
	int idx;
	int len;
	data* next;
	void init() {
		next = nullptr, str = nullptr, idx = len = 0;
	}
	data* alloc(data* np, int i) {
		str = word[i], next = np, len = wlen[i], idx = i;
		return this;
	}
} buf[10010], * htab[10][10]; //10개로 나눠서 넣음, 그안에 또 10개, 1개짜리는 0번에 넣음

inline int hashF(char* s) {
	return s[0] ? (s[0] - '0') : s[0];
}
void Init() {
	bcnt = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			data* p = htab[i][j];
			while (p) {
				data* tmp = p->next;
				p->init();
				p = tmp;
			}
			htab[i][j] = nullptr;
		}
		wcnt[i] = 0;
	}
	for (int i = 0; i < N; i++) {
		wlen[i] = 0; word[i][0] = 0;
	}
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		Init();
		scanf("%d", &N);
		for (int n = 0; n < N; n++) {
			scanf("%s", word + n);
			int hidx1 = hashF(word[n]);
			int hidx2 = hashF(&word[n][1]);
			wcnt[hidx1]++;
			wlen[n] = strlen(word[n]);
			htab[hidx1][hidx2] = buf[bcnt++].alloc(htab[hidx1][hidx2], n); //해시삽입, 맨 앞에 밀어넣기
		}//해시테이블 완성
		int find = 0;
		for (int i = 0; i < N; i++) { //접두사 찾기
			int hidx1 = hashF(word[i]);
			int hidx2 = hashF(&word[i][1]);

			if (wcnt[hidx1] > 1 && wlen[i] == 1) {
				find = 1; break;
			}
			for (data* p = htab[hidx1][hidx2]; p; p = p->next) {
				if (p == nullptr) break;
				if (p->str == word[i]) continue; //나 자신임
				if (wlen[i] < p->len) //접두사 가능한 경우
					if (strncmp(p->str, word[i], wlen[i]) == 0) { //일치하면
						find = 1;
						break;
					}
			}
		}
		if (find) printf("NO\n");
		else printf("YES\n");
	}

	return 0;
}