와일드카드.txt

10 100
18
100
200 frog
200 flag
200 flag
200 play
400 fl*g 2
400 f*g 3
300 flag 2
400 flag 0
200 slay
200 slayer
200 slave
400 slay* 2
300 *lay 2
400 s* 2
400 * 3
300 * 3
400 * 0
30
100
200 v
200 xz
200 khuiyo
300 bqylkz 0
200 e
400 *l 0
400 adizbu 0
200 wfxge
200 ohydf
400 k*ub 0
200 stjwk
200 v
200 sxlej
200 uajyu
200 c
300 e 1
400 v 2
200 vd
400 fe* 0
300 tfkju 0
400 * 11
400 *ohydf 1
200 lb
200 kxcslm
200 f
200 sxicro
400 *u 1
200 u
200 xj
300
100
200 nkazve
400 hvzenl 0
200 qjcq
200 ep
200 croayl
300 bi 0
400 * 4
200 ixfs
200 aqwsvl
200 qox
200 uu
200 n
200 pn
200 x
200 psgzp
200 snvyq
200 qcvsni
200 ufqlss
400 gsty 0
200 a
400 pj* 0
400 a*wsvl 1
400 pn 1
400 ttw 0
400 dls 0
200 fkppq
400 nhji 0
200 ihd
400 m* 0
400 *tpdm 0
300 ihd 1
400 aqwsvl 1
200 ucym
400 *s 2
400 pn* 1
200 a
300 uu 1
200 vhutr
200 jqhoaq
200 uqrll
200 v
400 q*bf 0
200 dnpduf
400 xmrywq 0
400 hoaq 0
200 ksqyo
200 tmh
200 ryjqfj
400 z*z 0
200 zffpi
200 mihin
300 zffpi 1
200 vbbir
200 ah
400 eay 0
200 daygwz
200 ajapbz
200 vprdw
400 uqrll 1
200 jqkj
200 wbekd
400 st* 0
400 hez*dz 0
200 giqh
200 l
200 v
200 ro
200 irfor
200 cq
400 v 2
200 muptn
200 rhp
200 rytk
200 e
200 bgxpwr
400 nyf 0
200 gjhgcd
200 wfb
400 cwiezv 0
200 jqbrdk
200 badu
300 v 2
200 zvxk
200 txgh
400 f 0
200 o
200 oeqkka
200 y
200 n
400 *rdk 1
200 qadqc
200 como
200 a
200 hge
400 d* 2
200 dtlv
200 foy
200 maxy
200 cajwx
200 goe
400 rytk 1
400 *kz 0
200 ondk
200 yqrjjb
200 zesm
200 jc
300 oglo 0
200 lemfnh
200 vjfztl
200 flv
400 b* 2
200 routpn
200 n
400 w* 2
200 xgqd
200 qen
200 vzp
200 lqb
400 eiopmk 0
400 fmb* 0
200 u
200 tveeah
200 ivusf
200 n
400 * 79
200 cuh
200 s
200 py
300 n 4
200 owdofh
200 xbpvdl
200 on
400 * 81
200 zqvkh
200 wkibg
400 dm*jzm 0
200 ncxo
200 wd
300 sylj 0
400 js*i 0
200 rkpzo
400 *disew 0
300 iay 0
400 w*y 0
400 * 86
200 al
200 z
200 lvwjf
200 hmhnuc
200 okzf
200 mrmeps
400 *b 3
200 xk
200 txose
200 yuz
200 ixkvho
200 e
200 aog
200 yqmgv
200 dymp
200 stepda
200 irpwi
200 b
400 hh* 0
200 kdm
400 b* 3
400 oaep*f 0
200 jgnwme
200 uar
400 l* 4
400 mj*ez 0
200 x
200 tqltba
200 hoaxl
200 vymj
200 v
200 tifdf
200 zhav
400 evb 0
200 zif
200 vlabv
200 vlakfi
200 ekfx
200 tej
400 dvm 0
200 kwarba
200 holq
300 qox 1
400 *mgv 1
200 eosz
400 ee* 0
200 fsfzag
200 fxkwfu
200 nss
200 q
200 fohkpl
200 jg
200 jed
200 zcmzsc
200 zaukzw
200 ybvq
200 n
200 orserk
400 *yx 0
400 *abdv 0
200 tv
200 rhk
200 ahozr
400 ne 0
200 jy
200 upnxpt
200 wm
400 yxx* 0
200 aqokrr
200 tfra
200 ipphs
200 gg
200 gqvz
400 vzp 1
200 l
200 v
400 *k 7
200 ogsahr
200 ixknxw
400 gg 1
400 *cd 1
300 tito 0
200 yb
400 *kn 0
200 vyus
300 nkazve 1
300 hzmj 0
300 maxy 1
200 mdfpe
200 m
200 ojht
200 teb
200 ibu
400 qf* 0
200 dub
200 sdw
200 k
200 bs
200 fbc
200 mrkkrd
400 tfra 1
400 fsfzag 1
200 j
200 dokfj
400 z*og 0
200 gyem
400 rt 0
400 xgqd 1
200 rubzb
200 t
200 qpse
200 oz
200 vgh
200 gno
200 f
200 elksab
200 sbgoz
200 soqawm
200 bk
200 v
400 *m 7
200 mci
200 o
200 zxerwo
400 ukgj 0
200 rcufh
200 wt
200 blv
200 ubgcv
200 k
200 gqrlr
400 zw 0
200 x
200 zkl
200 dldw
200 whnls
400 gq*gu 0
200 v
400 e*sz 1
300 oz 1
300 dokfj 1
400 vrkxzm 0
300 thfq 0
400 c*uh 1
200 p
200 dlcd
200 w
200 zhfx
400 * 189
300 wynyfg 0
400 jqhoaq 1
400 t 1
400 *ss 2
300 w 1

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

// API Command
#define CMD_INIT        100
#define CMD_ADDWORD     200
#define CMD_REMOVEWORD  300
#define CMD_SEARCHWORD  400

// User Implement API
extern void init(void);
extern void addWord(char str[]);
extern int  removeWord(char str[]);
extern int  searchWord(char str[]);

#define STRLEN_MAX 6

static int run(int score)
{
	int queryCnt;
	scanf("%d", &queryCnt);
	
	for (int q = 0; q < queryCnt; ++q)
	{
		int cmd;
		scanf("%d", &cmd);
		
		if (cmd == CMD_INIT)
		{
			init();
		}
		else if (cmd == CMD_ADDWORD)
		{
			char str[STRLEN_MAX + 1];
			scanf("%s", str);

			addWord(str);
		}
		else if (cmd == CMD_REMOVEWORD)
		{
			char str[STRLEN_MAX + 1];
			scanf("%s", str);

			int userAns = removeWord(str);

			int ans;
			scanf("%d", &ans);
			
			if (userAns != ans)
			{
				score = 0;
			}
		}
		else if (cmd == CMD_SEARCHWORD)
		{
			char str[STRLEN_MAX + 1];
			scanf("%s", str);

			int userAns = searchWord(str);

			int ans;
			scanf("%d", &ans);
			
			if (userAns != ans)
			{
				score = 0;
			}
		}
	}
	return score;
}

int main(void)
{
	setbuf(stdout, NULL);
	
	//freopen("sample_input.txt", "r", stdin);
	
	int TC;
	int targetScore;
	scanf("%d %d", &TC, &targetScore);
	
	for (int testcase = 1; testcase <= TC; ++testcase)
	{
		int score = run(targetScore);
		printf("#%d %d\n", testcase, score);
	}
	
	return 0;
}

struct Node {
    int cnt;
    int endCnt;
    Node* alphabet[26];
    Node* parent;
};
 
Node node[600002];
 
int nodeCnt;
int result;
Node* head;
Node* rhead;
 
Node* getAlphabet() {
    node[nodeCnt].endCnt = node[nodeCnt].cnt = 0;
    node[nodeCnt].parent = nullptr;
    for (register int i = 0; i < 26; ++i) {
        node[nodeCnt].alphabet[i] = nullptr;
    }
    return &node[nodeCnt++];
}
 
void reserveStr(char a[], char b[], int len) {
    int j = len;
    for (int i = 0; i < len; i++) {
        a[--j] = b[i];
    }
    a[len] = '\0';
}
 
int mstrcmp(const char a[], const char b[]);
void mstrcpy(char dest[], const char src[]);
int mstrlen(const char a[]);
 
 
void init(void)
{
    nodeCnt = 0;
    head = getAlphabet();
    rhead = getAlphabet();
}
 
void addWord2Node(Node* tmp, char str[]) {
    if (*str == '\0')
    {
        tmp->endCnt++;
        return;
    }
    tmp->cnt++;
    int index = *str - 'a';
    if (tmp->alphabet[index])
    {
        addWord2Node(tmp->alphabet[index], (str + 1));
    }
    else
    {
        tmp->alphabet[index] = getAlphabet();
        tmp->alphabet[index]->parent = tmp;
        addWord2Node(tmp->alphabet[index], str + 1);
    }
}
void addWord(char str[])
{   
    int length = mstrlen(str);
    addWord2Node(head, str);    
 
    char rstr[7];
    reserveStr(rstr, str, length);
    addWord2Node(rhead, rstr);
}
 
int calculate_searchword(Node* st, const char* str, bool isRemove = false) {
    int res = 0;
    if (*str == '\0')
    {
        res = st->endCnt;
        if (isRemove)
        {
            st->endCnt = 0;
            register Node* tmp = st->parent;
            while (tmp)
            {
                tmp->cnt -= res;
                tmp = tmp->parent;
            }
        }
        return res;
    }
 
    if (*str != '*')
    {
        int index = *str - 'a';
        if (st->alphabet[index])
        {
            res += calculate_searchword(st->alphabet[index], str + 1, isRemove);         
        }
    }
    else
    {
        if (*(str + 1) == '\0')
        {
            res = st->endCnt + st->cnt;
            if (isRemove)
            {
                st->endCnt = 0;
                st->cnt = 0;
                for (register int i = 0; i < 26; i++)
                {
                    st->alphabet[i] = nullptr;
                }
                register Node* tmp = st->parent;
                while (tmp)
                {
                    tmp->cnt -= res;
                    tmp = tmp->parent;
                }
            }
        }
        else
        {
            for (register int i = 0; i < 26; i++)
            {
                if (st->alphabet[i])
                {
                    if (i == *(str + 1) - 'a')
                    {
                        res += calculate_searchword(st->alphabet[i], str + 2, isRemove);
                    }
                    res += calculate_searchword(st->alphabet[i], str, isRemove);                 
                }
            }
        }
    }
    return res;
}
 
int removeWord(char str[])
{   
    if (str[0] == '*' && str[1] == '\0') {
        int result = head->cnt;
        init();
        return result;
    }
    int isWildCard = -1;
    int length = 0;
    char rstr[7];   
 
    for (int i = 0; str[i]; ++i) {
        if (str[i] == '*') {
            isWildCard = i;
        }
        ++length;
    }
    reserveStr(rstr, str, length);
     
    calculate_searchword(head, str, true);
    return calculate_searchword(rhead, rstr, true); 
}
 
int searchWord(char str[])
{   
    if (str[0] == '*' && str[1] == '\0')
        return head->cnt;
    int wildCard = -1;
    int length = 0;
     
    for (int i = 0; str[i]; ++i) {
        if (str[i] == '*') {
            wildCard = i;
        }
        ++length;
    }
    char rstr[7];
    reserveStr(rstr, str, length);
 
    if (wildCard >= length / 2) {
        return calculate_searchword(head, str);
    }   
    return calculate_searchword(rhead, rstr);
}
 
 
int mstrcmp(const char a[], const char b[])
{
    int i;
    for (i = 0; a[i] != '\0'; ++i) if (a[i] != b[i]) return a[i] - b[i];
    return a[i] - b[i];
}
 
void mstrcpy(char dest[], const char src[])
{
    int i = 0;
    while (src[i] != '\0') { dest[i] = src[i]; i++; }
    dest[i] = src[i];
}
 
int mstrlen(const char a[])
{
    int i;
    for (i = 0; a[i] != '\0'; ++i);
    return i;
}