Digitalni katalog

Bibliotekarka pravi digitalni katalog knjiga. Nakon unosa svih naslova, katalog se sortira po abecedi korišćenjem qsort, a zatim stiže lista zahteva čitaoca. Za svaki traženi naslov treba proveriti da li se nalazi u katalogu primenom binarne pretrage.

Ulaz

Sa standardnog ulaza unose se dva cela broja $n$ i $m$ ($1 \leq n, m \leq 10^6$). Zatim se unosi $n$ naziva knjiga (do $40$ karaktera), po jedan u svakoj liniji. Nakon toga, unosi se $m$ zahteva (takođe, do $40$ karaktera).

Izlaz

Na standardni izlaz, za svaki zahtev, ispisati DA ukoliko se knjiga nalazi u katalogu, inače ispisati NE.

Primer

Ulaz

5 4
Algoritmi
MalaPrinca
Matrica
Nizovi101
Slikovnica
MalaPrinca
ZimskaPesma
Algoritmi
Nizovi101

Izlaz

DA
NE
DA
DA

Rešenje

`main.c`

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TITLE_LEN 40

static int cmp_title(const void *lhs, const void *rhs)
{
	const char *a = lhs;
	const char *b = rhs;
	return strcmp(a, b);
}

static int cmp_key(const void *key, const void *elem)
{
	const char *a = key;
	const char *b = elem;
	return strcmp(a, b);
}

int main(void)
{
	size_t n, m;

	scanf("%zu %zu", &n, &m);

	size_t sizeof_title = (TITLE_LEN + 1) * sizeof (char);

	char (*titles)[TITLE_LEN + 1] = malloc(n * sizeof_title);
	if (titles == NULL) {
		exit(EXIT_FAILURE);
	}

	for (size_t i = 0; i < n; i++) {
		scanf("%s", titles[i]);
	}

	qsort(titles, n, sizeof_title, cmp_title);

	char query[TITLE_LEN];

	for (size_t i = 0; i < m; i++) {
		scanf("%s", query);
		void *found = bsearch(query, titles, n, sizeof_title, cmp_key);
		if (found == NULL) {
			printf("NE\n");
		} else {
			printf("DA\n");
		}
	}

	free(titles);

	exit(EXIT_SUCCESS);
}