Matching on Array

Alice has a sequence $\{a_1, a_2, \dots, a_n\}$ with $n$ positive integers. Bob has some positive integer sequences with different size. Alice wants to know the total occurrences of every sequence Bob has in Alice's sequence (the occurrences are allowed to overlap).

We say one sequence $B$ occurs in another sequence $A$ if there is a contiguous subsequence of $A$ that is the same as $B$ after scaled by a positive real factor.

For example $A=\{2,4,8,16\}, B = \{1, 2\}$ then $B$ occurs three times in $A$. The occurrences are $\{2, 4\}$, $\{4,8\}$ and $\{8, 16\}$. And the factor is 0.5, 0.25 and 0.125.

There are multiple test cases. The first line of input contains an integer $T\ (1 \le T \le 30)$, indicating the number of test cases. For each test case:

The first line contains two integer $n$ and $m$ $(1 \le n, m \le 100000)$, indicating the size of Alice's sequence and the number of sequences Bob has. In the next line, there are $n$ integers, $a_1, a_2, \dots, a_n$, indicating Alice's sequence. In the following $m$ lines, each starts with an integer $k_i (1 \le k_i \le 300000)$ - the size of the sequence. Then $k_i$ space separated positive integers follow, indicating the sequence.

The total sum of $k_i$ is less than or equal to 1000000. Other integers are between 1 and 10000, inclusive.

For each test case, output a single line with a single integer, indicating the total number of occurrences.

2
4 1
2 4 8 16
2 1 2
5 3
2 4 2 4 6
3 1 2 1
1 5
2 16 8

3
7

For sample 1, please refer to the problem description. For sample 2, {1, 2, 1} occurs only once, {5} occurs five times and {16, 8} occurs only once.

BestCoder Round #27