include stdio include stdlib struct pattern struct pattern and struct

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <stdio.h>
#include <stdlib.h>
struct pattern
{
struct pattern *and;
struct pattern *or;
char symbol;
};
typedef enum {
false, true
} bool;
#define NewLine '\n'
#define Space ' '
#define _getc getchar_unlocked()
#define _putc putchar_unlocked
#define _parse_integer(val, sep) \
do { \
char token; \
val = 0; \
while ((token = _getc) != sep) val = val * 10 + token - 48; \
} while (0);
#define _read_string(s) \
do { \
char *p = s; \
while ((*p = _getc) != '\n') ++p; \
*p = '\0'; \
} while (0);
#define _read_pattern(p) \
do { \
char token; \
bool mark = false; \
struct pattern *current = p, *old = p; \
while ((token = _getc) != NewLine) \
{ \
switch (token) \
{ \
case '(': \
mark = true; \
old = current; \
break; \
case ')': \
mark = false; \
current = old->and = _new_pattern(); \
break; \
default: \
current->symbol = token; \
if (mark) \
{ \
current = current->or = _new_pattern(); \
} \
else \
{ \
current = current->and = _new_pattern(); \
} \
} \
} \
} while (0);
#define MAX_WORD_LEN (15 + 5)
#define MAX_WORDS 5000
#define MAX_TEST_CASES 500
static struct pattern *
_new_pattern (void)
{
struct pattern *p = (struct pattern *) malloc (sizeof (struct pattern));
p->and = p->or = NULL;
return p;
}
bool
pattern_match (struct pattern *p, const char *word)
{
struct pattern *current = p, *old;
const char *pos = word;
while (current != NULL)
{
if (*pos != current->symbol)
{
if (current->or != NULL)
{
old = current;
current = current->or;
while (current != NULL)
{
if (current->symbol == *pos)
{
break;
}
current = current->or;
}
if (current != NULL)
{
current = old;
goto match;
}
else
{
return false;
}
}
else
{
return false;
}
}
else
{
match: current = current->and;
pos = pos + 1;
}
}
return true;
}
int
main (int argc, char **argv)
{
char words[MAX_WORDS][MAX_WORD_LEN];
struct pattern patterns[MAX_TEST_CASES];
int l, d, n, i, j, c;
_parse_integer (l, Space);
_parse_integer (d, Space);
_parse_integer (n, NewLine);
for (i = 0; i < d; ++i)
{
_read_string (words[i]);
}
for (i = 0; i < n; ++i)
{
_read_pattern (patterns + i);
c = 0;
for (j = 0; j < d; ++j)
{
if (pattern_match (patterns + i, words[j]))
{
++c;
}
}
printf ("Case #%d: %d\n", i + 1, c);
}
return 0;
}