{"problem":{"name":"[JOI Open 2016] 销售基因链 / Selling RNA Strands","description":{"content":"基因库中有 $N$ 个字符串，这些字符串仅由 `A`，`G`，`U`，`C` 组成（保证每个字符串都仅包含这四种字母）。 有 $M$ 组查询，每组查询包含两个字符串 $P,Q$，试求：基因库中有多少个字符串同时存在前缀 $P$ 和后缀 $Q$。 举个例子，`GAC` 存在前缀 `G`、`GA`、`GAC`，存在后缀 `C`、`AC`、`GAC`，那么我们可以说：`GAC` 同时存在前缀 `GA","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9196"},"statements":[{"statement_type":"Markdown","content":"基因库中有 $N$ 个字符串，这些字符串仅由 `A`，`G`，`U`，`C` 组成（保证每个字符串都仅包含这四种字母）。\n\n有 $M$ 组查询，每组查询包含两个字符串 $P,Q$，试求：基因库中有多少个字符串同时存在前缀 $P$ 和后缀 $Q$。\n\n举个例子，`GAC` 存在前缀 `G`、`GA`、`GAC`，存在后缀 `C`、`AC`、`GAC`，那么我们可以说：`GAC` 同时存在前缀 `GA` 和后缀 `AC`。\n\n## Input\n\n输入共 $N + M + 1$ 行。\n\n第一行有两个整数 $N, M$。  \n在接下来的 $N$ 行中，每行一个字符串 $S_i$，表示基因库中的一个字符串。  \n在接下来的 $M$ 行中，每行有两个用空格分隔的字符串，表示一组查询。\n\n## Output\n\n输出共 $M$ 行，每行一个整数，表示符合查询条件的字符串的数量。\n\n[samples]\n\n## Background\n\n**译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T2 「RNA 鎖の販売 / Selling RNA Strands」**\n\n## Note\n\n### 样例 1 解释\n\n第一组查询：无法找到；  \n第二组查询：`AUGC` 满足条件；  \n第三组查询：`AUGC` 和 `AGC` 满足条件。\n\n### 样例 2 解释\n\n注意基因库中的字符串可以重复。\n\n### 数据规模与约定\n\n**本题采用捆绑测试**。\n\n对于所有数据，$1\\le N, M \\leq 10 ^ 5$，$1 \\leq |S_i|, |P_j|, |Q_j| \\le 10^5$，$1\\le\\sum |S_i|, \\sum |P_j|, \\sum |Q_j| \\le 2\\times 10^6$。\n\n- Subtask 1（10 points）：$N, M, |S_i|, |P_j|, |Q_j| \\le 100$。\n- Subtask 2（25 points）：$N, M\\le 5000$。\n- Subtask 3（25 points）：$\\sum |S_i|, \\sum|P_j|, \\sum |Q_j| \\le 10^5$。\n- Subtask 4（40 points）：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9196","tags":["2016","字典树 Trie","AC 自动机","JOI（日本）"],"sample_group":[["2 3\nAUGC\nAGC\nG C\nAU C\nA C","0\n1\n2"],["3 3\nAA\nAA\nAGA\nAA AA\nAG GA\nAG GA","2\n1\n1"],["8 7\nGCGCUACCCCAACACAAGGCAAGAUAUA\nG\nGGAC\nGCGG\nU\nGCGCUACCCCAACACAAGGCAAGAUGGUC\nGCCG\nGCGCUGA\nGCGCUACCC A\nGCGCUACCCC AC\nGCG C\nGCGC A\nG G\nG C\nG GGA","1\n0\n1\n2\n3\n2\n0"]],"created_at":"2026-03-03 11:09:25"}}