4.前缀询问

题目描述

有 $n$ 个字符串 $T_1$ , $T_2$ , $\cdots$ , $T_n$ ，给出 $m$ 个询问，对于第 $i$ 个询问，给出一个字符串 $S_i$ 。

对于每个询问，我们可以得到一个长度为 $n$ 的布尔数组 $a$ ，其中 $a_j=[prefix(T_j)=S_i]$ （其中 $prefix(T_j)=S_i$ 表示 $S_i$ 是否是 $T_j$ 的前缀）。

例如， $a=[0,0,1]$ 则表示 $S_i$ 只是 $T_3$ 的前缀，而不是 $T_1$ , $T_2$ 的前缀。

对于每个询问，要求求出 $a$ 数组的最长全 $0$ 子串长度。

第一行两个数 $n$ ， $m$ ，表示有 $n$ 个字符串， $m$ 个询问。

接下来 $n$ 行，每行一个字符串 $T_i$ 。

再接下来 $m$ 行，每行一个字符串 $S_i$ 。

对于每个询问，输出 $a$ 数组的最长全 $0$ 子串长度。

对于 $10\%$ 的数据， $1 \leq n \leq 10^2$ ， $1 \leq m \leq 10^2$ ， $1 \leq |T_i| \leq 10^2$ ， $1 \leq \sum |S_i| \leq 10^3$ ；
对于 $30\%$ 的数据， $1 \leq n \leq 10^3$ ， $1 \leq m \leq 10^3$ ， $1 \leq |T_i| \leq 10^3$ ， $1 \leq \sum |S_i| \leq 10^4$ ；
对于 $100\%$ 的数据， $1 \leq n \leq 10^5$ ， $1 \leq m \leq 10^5$ ， $1 \leq |T_i| \leq 5 \times 10^6$ ， $1 \leq \sum |S_i| \leq 3 \times 10^6$ 。

字符串中只包含 $a$ ， $b$ ， $c$ 三种字母，数据随机。其中 $|T_i|$ 、 $|S_i|$ 分别表示字符串 $T_i$ 、 $S_i$ 的长度

3 2
abcabc
aabc
abbc
aa
ba

1
3