[JOI Open 2016] 销售基因链 / Selling RNA Strands

Luogu

IDLGP9196

Time1500ms

Memory1024MB

DifficultyP6

2016字典树 TrieAC 自动机JOI（日本）

基因库中有 $N$ 个字符串，这些字符串仅由 `A`，`G`，`U`，`C` 组成（保证每个字符串都仅包含这四种字母）。有 $M$ 组查询，每组查询包含两个字符串 $P,Q$，试求：基因库中有多少个字符串同时存在前缀 $P$ 和后缀 $Q$。举个例子，`GAC` 存在前缀 `G`、`GA`、`GAC`，存在后缀 `C`、`AC`、`GAC`，那么我们可以说：`GAC` 同时存在前缀 `GA` 和后缀 `AC`。 ## Input 输入共 $N + M + 1$ 行。第一行有两个整数 $N, M$。在接下来的 $N$ 行中，每行一个字符串 $S_i$，表示基因库中的一个字符串。在接下来的 $M$ 行中，每行有两个用空格分隔的字符串，表示一组查询。 ## Output 输出共 $M$ 行，每行一个整数，表示符合查询条件的字符串的数量。 [samples] ## Background **译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T2 「RNA 鎖の販売 / Selling RNA Strands」** ## Note ### 样例 1 解释第一组查询：无法找到；第二组查询：`AUGC` 满足条件；第三组查询：`AUGC` 和 `AGC` 满足条件。 ### 样例 2 解释注意基因库中的字符串可以重复。 ### 数据规模与约定 **本题采用捆绑测试**。对于所有数据，$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$。 - Subtask 1（10 points）：$N, M, |S_i|, |P_j|, |Q_j| \le 100$。 - Subtask 2（25 points）：$N, M\le 5000$。 - Subtask 3（25 points）：$\sum |S_i|, \sum|P_j|, \sum |Q_j| \le 10^5$。 - Subtask 4（40 points）：没有额外限制。

Samples

Input #1

2 3
AUGC
AGC
G C
AU C
A C

Output #1

0
1
2

Input #2

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

Output #2

2
1
1

Input #3

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA

Output #3

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments