Gene bank - MarisaOJ: Marisa Online Judge

A gene can be represented as a string consisting of four characters

A

$A$ ,

U

$U$ ,

G

$G$ , and

C

$C$ . A gene bank contains

n

$n$ genes. Given

q

$q$ queries, each query consists of two strings

P

$P$ and

Q

$Q$ , and the task is to count how many strings in the gene bank have

P

$P$ as a prefix and

Q

$Q$ as a suffix. ### Input - The first line contains two integers

n

$n$ and

q

$q$ . - The next

n

$n$ lines, each contains a string

S_{i}

$S_i$ , representing a gene in the gene bank. - The next

q

$q$ lines, each contains two strings

P_{i}

$P_i$ and

Q_{i}

$Q_i$ , representing a query. ### Output - For each query, print an integer representing the number of strings that have

P_{i}

$P_i$ as a prefix and

Q_{i}

$Q_i$ as a suffix. ### Constraints -

1 \leq n, q, | S_{i} |, | P_{i} |, | Q_{i} | \leq 10^{5}

$1 \leq n, q, |S_i|, |P_i|, |Q_i| \leq 10^5$ . -

\sum | S_{i} |, \sum | P_{i} |, \sum | Q_{i} | \leq 2 \times 10^{6}

$\sum |S_i|, \sum |P_i|, \sum |Q_i| \leq 2 \times 10^6$ . ### Example Input:

23 A U G C A G C G C A U C A C

$2 3 AUGC AGC G C AU C A C$

Output:

012

$0 1 2$

### Subtasks - Subtask 1 (10% of the points):

1 \leq n, q, | S_{i} |, | P_{i} |, | Q_{i} | \leq 100

$1 \leq n, q, |S_i|, |P_i|, |Q_i| \leq 100$ . - Subtask 2 (25% of the points):

n, q \leq 5000

$n, q \leq 5000$ . - Subtask 3 (25% of the points):

\sum | S_{i} |, \sum | P_{i} |, \sum | Q_{i} | \leq 10^{5}

$\sum |S_i|, \sum |P_i|, \sum |Q_i| \leq 10^5$ . - Subtask 4 (40% of the points): No additional constraints.

Topic

Data structure

String

Rating

2200

Solution (0)

Solution