{"problem":{"name":"G. Bathroom terminal","description":{"content":"Smith wakes up at the side of a dirty, disused bathroom, his ankle chained to pipes. Next to him is tape-player with a hand-written message \"Play Me\". He finds a tape in his own back pocket. After put","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF852G"},"statements":[{"statement_type":"Markdown","content":"Smith wakes up at the side of a dirty, disused bathroom, his ankle chained to pipes. Next to him is tape-player with a hand-written message \"Play Me\". He finds a tape in his own back pocket. After putting the tape in the tape-player, he sees a key hanging from a ceiling, chained to some kind of a machine, which is connected to the terminal next to him. After pressing a Play button a rough voice starts playing from the tape:\n\n\"Listen up Smith. As you can see, you are in pretty tough situation and in order to escape, you have to solve a puzzle.\n\nYou are given _N_ strings which represent words. Each word is of the maximum length _L_ and consists of characters '_a_'-'_e_'. You are also given _M_ strings which represent patterns. Pattern is a string of length  ≤  _L_ and consists of characters '_a_'-'_e_' as well as the maximum 3 characters '_?_'. Character '_?_' is an unknown character, meaning it can be equal to any character 'a'-'e', or even an empty character. For each pattern find the number of words that matches with the given pattern. After solving it and typing the result in the terminal, the key will drop from the ceiling and you may escape. Let the game begin.\"\n\nHelp Smith escape.\n\n## Input\n\nThe first line of input contains two integers _N_ and _M_ (1 ≤ _N_ ≤  100 000, 1 ≤ _M_ ≤  5000), representing the number of words and patterns respectively.\n\nThe next _N_ lines represent each word, and after those _N_ lines, following _M_ lines represent each pattern. Each word and each pattern has a maximum length _L_ (1 ≤ _L_ ≤ 50). Each pattern has no more that three characters '_?_'. All other characters in words and patters are lowercase English letters from '_a_' to '_e_'.\n\n## Output\n\nOutput contains _M_ lines and each line consists of one integer, representing the number of words that match the corresponding pattern.\n\n[samples]\n\n## Note\n\nIf we switch '?' with 'b', 'e' and with empty character, we get 'abc', 'aec' and 'ac' respectively.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"史密斯在一间肮脏废弃的浴室旁醒来，脚踝被锁在管道上。旁边有一台录音机，上面贴着一张手写纸条：“播放我”。他从自己后口袋里找到一盘磁带。将磁带放入录音机后，他看到天花板上挂着一把钥匙，钥匙被锁在某种机器上，而该机器连接着他身旁的终端。按下播放键后，磁带中传出粗哑的声音：\n\n“听好了，史密斯。正如你所见，你处境艰难，要想逃脱，你必须解决一个谜题。\n\n给你 #cf_span[N] 个字符串，代表单词。每个单词的最大长度为 #cf_span[L]，由字符 '_a_'-'_e_' 组成。你还得到 #cf_span[M] 个字符串，代表模式。模式是一个长度为 #cf_span[ ≤  L] 的字符串，由字符 '_a_'-'_e_' 以及最多三个字符 '_?_' 组成。字符 '_?_' 代表未知字符，它可以等于任意字符 'a'-'e'，甚至可以是空字符。对于每个模式，找出与之匹配的单词数量。解决后将结果输入终端，钥匙将从天花板掉落，你便可逃脱。游戏开始。\n\n帮助史密斯逃脱。\n\n输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[M]（#cf_span[1 ≤ N ≤  100 000]，#cf_span[1 ≤ M ≤  5000]），分别表示单词和模式的数量。\n\n接下来的 #cf_span[N] 行表示每个单词，之后的 #cf_span[M] 行表示每个模式。每个单词和每个模式的最大长度为 #cf_span[L]（#cf_span[1 ≤ L ≤ 50]）。每个模式中 '_?_' 的数量不超过三个。单词和模式中的其他字符均为小写英文字母 '_a_' 到 '_e_'。\n\n输出包含 #cf_span[M] 行，每行一个整数，表示与对应模式匹配的单词数量。\n\n若将 '?' 分别替换为 'b'、'e' 和空字符，我们分别得到 'abc'、'aec' 和 'ac'。\n\n## Input\n\n输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[M]（#cf_span[1 ≤ N ≤  100 000]，#cf_span[1 ≤ M ≤  5000]），分别表示单词和模式的数量。接下来的 #cf_span[N] 行表示每个单词，之后的 #cf_span[M] 行表示每个模式。每个单词和每个模式的最大长度为 #cf_span[L]（#cf_span[1 ≤ L ≤ 50]）。每个模式中 '_?_' 的数量不超过三个。单词和模式中的其他字符均为小写英文字母 '_a_' 到 '_e_'。\n\n## Output\n\n输出包含 #cf_span[M] 行，每行一个整数，表示与对应模式匹配的单词数量。\n\n[samples]\n\n## Note\n\n若将 '?' 分别替换为 'b'、'e' 和空字符，我们分别得到 'abc'、'aec' 和 'ac'。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ denote the number of words and patterns, respectively.  \nLet $ W = \\{w_1, w_2, \\dots, w_N\\} $ be a set of words, where each $ w_i \\in \\{a,b,c,d,e\\}^* $ and $ 1 \\leq |w_i| \\leq L $.  \nLet $ P = \\{p_1, p_2, \\dots, p_M\\} $ be a set of patterns, where each $ p_j \\in (\\{a,b,c,d,e\\} \\cup \\{?\\})^* $, $ 1 \\leq |p_j| \\leq L $, and each $ p_j $ contains at most three occurrences of the character `?`.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 100{,}000 $  \n2. $ 1 \\leq M \\leq 5{,}000 $  \n3. $ 1 \\leq L \\leq 50 $  \n4. Each pattern $ p_j $ contains at most three `?` characters.  \n5. All characters in words and patterns are from the set $ \\{a,b,c,d,e\\} $, except `?` in patterns.\n\n**Objective**  \nFor each pattern $ p_j \\in P $, compute:  \n$$\nf(p_j) = \\left| \\left\\{ w_i \\in W \\mid w_i \\text{ matches } p_j \\right\\} \\right|\n$$  \nwhere a word $ w_i $ matches a pattern $ p_j $ if there exists a way to replace each `?` in $ p_j $ with **either** one character from $ \\{a,b,c,d,e\\} $ **or** the empty string $ \\varepsilon $, such that the resulting string equals $ w_i $.\n\n(Note: Each `?` can be independently replaced by any one of the 6 options: $ a,b,c,d,e,\\varepsilon $, and replacements are done simultaneously across all `?` in the pattern.)","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF852G","tags":["implementation"],"sample_group":[["3 1\nabc\naec\nac\na?c","3"]],"created_at":"2026-03-03 11:00:39"}}