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

char *compileglob(const char *pattern)
{
	char *compiled, *ptr;
	compiled = malloc(strlen(pattern)+1);
	if (!compiled) {
		perror("malloc");
		exit(EXIT_FAILURE);
	}
	ptr = compiled;
	/* Coalesce runs of star operators */
	while (*pattern) {
		if (*pattern != '*' || ptr == compiled || ptr[-1] != '*')
			*ptr++ = *pattern;
		++pattern;
	}
	return compiled;
}

int checkglob(const char *pattern, const char *text)
{
	size_t n, statescount, nextstatescount, i, prev;
	size_t *states, *nextstates;
	int accepting;

	n = strlen(pattern) + 1;

	statescount = nextstatescount = 0;

	states = malloc(2 * n * sizeof(size_t));
	if(states == 0) {
		perror("malloc");
		exit(EXIT_FAILURE);
	}

	nextstates = states + n;

	/* Set initial states */
	states[0] = 0;
	statescount = 1;
	if(pattern[0] == '*') {
		states[1] = 1;
		statescount = 2;
	}

	/* Simulate the NFA (each state = index into pattern) */
	for (;;) {
		nextstatescount = 0;
		prev = (size_t) -1;

		for (i = 0; i < statescount; ++i) {
			size_t state = states[i];
			if (pattern[state] == '*') {
				/* Star - expect arbitrary number of chars */
				if (prev != state) {
					nextstates[nextstatescount++] = state;
				}
				nextstates[nextstatescount++] = state + 1;
				prev = state + 1;
			} else if (pattern[state] == '?') {
				/* Question mark - expect single char */
				if (*text) {
					nextstates[nextstatescount++] = state + 1;
					prev = state + 1;
				}
			} else if (pattern[state]) {
				/* Normal state - expect specific char */
				if (*text == pattern[state]) {
					nextstates[nextstatescount++] = state + 1;
					prev = state + 1;
				}
			} else {
				/* Accepting (final) state */
				if (!*text && prev != state) {
					nextstates[nextstatescount++] = state;
					prev = state;
				}
			}
		}

		if (nextstatescount == 0) {
			free(states);
			return 0;
		}
		if (!*text) {
			accepting = nextstates[nextstatescount - 1] == n - 1;
			free(states);
			return accepting;
		}

		memcpy(states, nextstates, nextstatescount * sizeof(size_t));
		statescount = nextstatescount;
		++text;
	}

	/* not reached */
	return 0;
}

int main(int argc, char **argv)
{
	int i;
	char *pattern;
	FILE *f;
	char buf[1024];

	if (argc<2)
		return EXIT_FAILURE;

	pattern = compileglob(argv[1]);
	for (i = 2; i < argc; ++i) {
		f = fopen(argv[i], "r");
		if (!f) {
			perror(argv[i]);
			return 1;
		}
		while (fgets(buf, sizeof buf, f)) {
			if (*buf && buf[strlen(buf)-1] == '\n')
				buf[strlen(buf)-1] = 0;
			if (checkglob(pattern, buf))
				puts(buf);
		}
		fclose(f);
	}
	free(pattern);
	return 0;
}