sabin

Sabin

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~}))$.

h2. Date de intrare

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.
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.

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.

h2. Date de ieşire

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

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ă.

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 |

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

| 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

|
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") ==