Dans les algorithmes de recherche, nous rencontrons souvent le problème suivant : il existe de nombreuses entrées et une séquence de mots-clés, et l'on souhaite trouver les entrées qui correspondent à ces mots-clés. Par exemple, l'entrée « 2025 China Collegiate Programming Contest (CCPC) Jinan Regional Contest » correspond aux mots-clés « 2025 CCPC Jinan ». Notez que la séquence de mots-clés n'a pas besoin d'apparaître consécutivement dans l'entrée ; il suffit qu'elle apparaisse comme une sous-séquence de l'entrée.
Sur la base de considérations pratiques, nous pouvons définir l'algorithme de pertinence suivant : sélectionner autant de sous-séquences sans chevauchement que possible dans l'entrée, de sorte que chaque sous-séquence soit exactement égale à la séquence de mots-clés donnée ; la pertinence est alors le nombre de sous-séquences sélectionnées.
Dans ce problème, chaque mot peut être représenté par un entier strictement positif. On donne une séquence de mots-clés de longueur $m$ ; pour simplifier le problème, les mots-clés sont tous distincts. De plus, $n$ entrées sont fournies, où la $i$-ème entrée est une séquence d'entiers strictement positifs de longueur $l_i$. Votre objectif est de calculer la pertinence de chaque entrée.
Entrée
La première ligne de l'entrée contient un entier $m$ ($1 \le m \le 10$), représentant la longueur de la séquence de mots-clés.
La ligne suivante contient $m$ entiers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le m$), représentant la séquence de mots-clés. Il est garanti que $b_1, b_2, \dots, b_m$ sont tous distincts.
La ligne suivante contient un entier $n$ ($1 \le n \le 100$), représentant le nombre d'entrées.
Pour les $n$ lignes suivantes : la $i$-ème ligne commence par un entier $l_i$ ($1 \le l_i \le 10^6$), représentant la longueur de la $i$-ème entrée, suivi de $l_i$ entiers $a_{i,1}, a_{i,2}, \dots, a_{i,l_i}$ ($1 \le a_{i,j} \le 10^6$), représentant le contenu de la $i$-ème entrée.
Il est garanti que la longueur totale de toutes les entrées ne dépasse pas $10^6$.
Sortie
Affichez $n$ lignes, où la $i$-ème ligne contient un entier représentant la pertinence de la $i$-ème entrée.
Exemple
Entrée
4 4 2 1 3 3 8 4 2 1 3 4 2 3 1 9 1 4 2 4 1 2 1 3 3 12 1 1 2 3 4 2 1 1 2 1 3 3
Sortie
1 2 1
Note
Ci-dessous, les séquences d'indices sont utilisées pour représenter les sous-séquences.
- Pour la première entrée, vous pouvez choisir $[1, 2, 3, 7]$ comme sous-séquence, auquel cas $[a_1, a_2, a_3, a_7] = [4, 2, 1, 3]$, ce qui est exactement égal à la séquence de mots-clés.
- Pour la deuxième entrée, vous pouvez choisir $[2, 3, 5, 9]$ et $[4, 6, 7, 8]$ comme sous-séquences. Notez que $[2, 3, 7, 9]$ et $[4, 6, 7, 9]$ ne peuvent pas être choisies simultanément car leurs positions se chevauchent.