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