销售基因链

题号：NC53175
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

译自 JOI Open 2016 T2 「RNA 鎖の販売 / Selling RNA Strands」

基因库中有N个字符串，这些字符串仅由A,G,U,C组成（保证每个字符串都包含四种字母）。
由M组查询，每组查询包含两个字符串P,Q，试求：基因库中有多少个字符串同时存在前缀P和后缀Q。
举个例子，GAC存在前缀G,GA,GAC，存在后缀C,AC,GAC，那么我们可以说：GAC同时存在前缀GA和后缀AC。

输入描述:

第一行有两个整数N,M。
在接下来的N行中，每行一个字符串，表示基因库中的一个字符串。
在接下来的M行中，每行有两个用空格分隔的字符串，表示一组查询。

输出描述:

输出共M行，每行一个整数，表示符合查询条件的字符串的数量。

示例1

输入

复制

2 3
AUGC
AGC
G C
AU C
A C

输出

复制

0
1
2

说明

第一组查询：找不到。
第二组查询：AUGC满足条件。
第三组查询：AUGC和AGC满足条件。

示例2

输入

复制

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

输出

复制

2
1
1

说明

注意基因库中的字符串可以重复。

示例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

输出

复制

备注:

对于所有数据，。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2742