Sabin

sabin

== include(page="template/taskheader" task_id="sabin") ==

p<>. Dat fiind ca mallu' nu era cea mai apropiată locaţie, Sabin s-a hotărât să petreacă ceva timp la bibliotecă. Aici el a dat peste două rafturi cu cărţi.

<>p. Dat fiind ca mallu' nu era cea mai apropiată locaţie, Sabin s-a hotărât să petreacă ceva timp la bibliotecă. Aici el a dat peste două rafturi cu cărţi.

p<>. Primul raft conţine $N$ compartimente de cărţi, fiecare compartiment având acelaşi număr de
cărţi, $K$. Cel de-al doilea raft conţine un singur compartiment cu $M$ cărţi. Toate cărţile din ambele rafturi au titlurile formate din **exact $P$** caractere mici ale alfabetului englez.

<>p. Primul raft conţine N compartimente de cărţi, fiecare compartiment având acelaşi număr de
cărţi, K. Cel de-al doilea raft conţine un singur compartiment cu M cărţi. Toate cărţile din ambele rafturi au titlurile formate din exact P caractere mici ale alfabetului englez.

p<>. Un prefix al unui şir de caractere se defineşte ca o subsecvenţă a şirului care începe de pe prima poziţie a acestuia. Definim **cel mai mare prefix comun** ({$maxprefix$}) a două şiruri de caractere ca fiind lungimea celei mai lungi secvenţe de caractere care este prefix şi al primului şir şi al celui de-al doilea.

<>p. Un prefix al unui şir de caractere se defineşte ca o subsecvenţă a şirului care începe de pe prima poziţie a acestuia. Definim cel mai mare prefix comun (maxprefix) a două şiruri de caractere ca fiind lungimea celei mai lungi secvenţe de caractere care este prefix şi al primului şir şi al celui de-al doilea.

p<>. Fiind date două compartimente de titluri de cărti $A=[c{~1~}, c{~2~}, ..., c{~K~}]$ şi $B=[d{~1~}, d{~2~}, ..., d{~K~}]$ definim **gradul de similitudine** al acestora ca fiind
$min(maxprefix(c{~1~}, d{~1~}), maxprefix(c{~2~}, d{~2~}), …, maxprefix(c{~K~}, d{~K~}))$.

<>p. Fiind date două compartimente de titluri de cărti A = [c1, c2, ..., cK] şi B = [d1, d2, .., dK] definim gradul de similitudine al acestora ca fiind min(maxprefix(c1, d1), maxprefix(c2, d2), …, maxprefix(cK, dK)).

p<>. Sabin ar dori să scoată $K$ cărţi din al doilea raft şi să găsească un compartiment din primul raft pentru care gradul de similitudine să aibă o valoare dată.

<>p. Sabin ar dori să scoată K cărţi din al doilea raft şi să găsească un compartiment din primul raft pentru care gradul de similitudine să aibă o valoare dată.

p<>. Ca să intraţi în graţiile lui Sabin având la dispozitie cele două rafuri de cărţi, trebuie să răspundeţi la $Q$ întrebări de forma: “Fiind date $K$ cărţi din al doilea raft, găsiţi toate compartimentele din primul raft care au gradul de similitudine cu compartimentul dat exact $X$ şi afişaţi numărul lor”.

<>p. Ca să intraţi în graţiile lui Sabin având la dispozitie cele două rafuri de cărţi, trebuie să răspundeţi la Q întrebări de forma: “Fiind date K cărţi din al doilea raft, găsiţi toate compartimentele din primul raft care au gradul de similitudine cu compartimentul dat exact X şi afişaţi numărul lor”.

h2. Date de intrare

p<>. Pe prima linie a fişierului $sabin.in$ se află $N, K, M, P$ şi $Q$. Următoarele $N$ linii descriu mulţimile de cărţi din primul raft: cea de-a $i$-a linie va conţine $K$ şiruri de caractere de lungime $P$, despărţite printr-un spaţiu, reprezentând cărţile din cel de-al $i$-lea compartiment. Următoarea linie descrie cele $M$ cărţi din al doilea raft.
 
p<>. Următoarele $Q$ linii vor conţine fiecare $K + 1$ numere. Primul număr reprezintă gradul de similitudine dorit $X$. Următoarele $K$ numere reprezintă indicii cărţilor din al doilea raft care formează noul compartiment.

Fişierul de intrare $sabin.in$ ...

h2. Date de ieşire

p<>. Fişierul sabin.out va conţine $Q$ linii, câte una pentru fiecare întrebare din fişierul de intrare, reprezentând numărul de compartimente din primul raft care satisfac cerinţa dată.

În fişierul de ieşire $sabin.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 20 000$
* $1 ≤ M ≤ 30 000$
* $1 ≤ Q ≤ 20 000$
* $1 ≤ K ≤ 15$
* $1 ≤ P ≤ 30$
* $0 ≤ X ≤ 30$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. sabin.in |_. sabin.out |

| 4 2 6 4 4
abcd trzs
gefd fasf
gefa fasx
fxxx txxx
affx trfs abxx trxx gefa fasf
1 1 2
1 3 4
3 5 6
1 6 2
| 1
0
2
1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

p<>. Numerele de pe prima linie a fişierului de intrare reprezintă $N = 4, K = 2, M = 6, P = 4$ şi $Q = 4$.
 
p<>. Primul raft este format din $N = 4$ compartimente. Fiecare compartiment are $K = 2$ cărţi, formate din $P = 4$ caractere: $[abcd, trzs] [gefd, fasf] [gefa, fasx], [fxxx, txxx]$.
 
p<>. Avem $M = 6$ cărţi pe al doilea raft: $affx, trfs, abxx, trxx, gefa, fasf$.
 
p<>. Primul query cere numărul de compartimente care să aibă coeficientul de similitudine cu $[affx, trfs]$ egal cu $1$. Doar compartimentul $[abcd, trzs]$ satisface cerinţa.
 
p<>. Al doilea query cere numărul de compartimente care să aibă coeficientul de similitudine cu $[abxx, trxx]$ egal cu $1$. Nu există niciun astfel de compartiment. Compartimentul $[abcd, trzs]$ are gradul de similitudine $2$.
 
p<>. Al treilea query cere numărul de compartimente care să aibă coeficientul de similitudine cu $[gefa, fasf]$ egal cu $3$. Soluţia este $[gefd, fasf]$ şi $[gefa, fasx]$.
 
p<>. Al patrulea query cere numărul de compartimente care să aibă coeficientul de similitudine cu $[fasf, trfs]$ egal cu $1$. Soluţia este $[fxxx, txxx]$.

...

== include(page="template/taskfooter" task_id="sabin") ==