Caracterele Muzicale

Preda, cât ai luat?
100
Pe albine, nu?
Da
Păi, albine e penală.
Da' tu ce-ai făcut, Dumitrache?
60

Cerință

Pentru șirul de caractere $s$, notăm $len(s)$ = lungimea șirului $s$. Definim $[l, r]$ din șirul $s$ = subsecvența de la $l$ la $r$ din șirul $s$ (de exemplu, $[3, 4]$ din șirul $abcdee$ = $cd$).

Definim $f(s, t)$, unde $s$ și $t$ sunt două șiruri de caractere astfel:

• Dacă $t$ nu se regăsește ca subșir în $s$, $f(s, t) = -1$;
• Altfel, $f(s, t)$ = lungimea maximă a unei subsecvențe $[l, r]$ pe care o putem scoate din $s$ astfel încât $t$ să se regăsească ca subșir în $s$ în continuare.

Dacă scoatem subsecvența $[l, r]$ din $s$, $s$ va deveni:
$s_1s_2s_3...s_{l-1}s_{r+1}s_{r+2}...s_{len(s)-1}s_{len(s)}$

Spunem că $t$ se regăsește ca subșir în $s$ dacă și numai dacă există $len(t)$ indici $1 \leq i_1 < i_2 < i_3 < i_4 < ... < i_{len(t)} \leq len(s)$ astfel încât $t_j=s_{i_j}$, unde $1 \leq j \leq len(t)$.

De exemplu, pentru $s = aabcd$ și $t = ac$, $f(s, t) = 2$, deoarece putem scoate subsecvența $[2, 3]$ din $s$, acesta devenind $acd$, iar $ac$ se regăsește ca subșir.

Pentru $s = ggggg$ și $t = a$, $f(s, t) = -1$, deoarece $t$ nu se regăseşte ca subşir în $s$.

Pentru exact $5$ perechi de șiruri $(s_i, t_i)$, să se afișeze $f(s_i, t_i)$.

Date de intrare

În fişierul de intrare carmuz.in, pe a $2 \cdot i$-a linie se găsește șirul $s_i$, iar pe a $2 \cdot i + 1$-a linie $t_i$, pentru $1 \leq i \leq 5$.

Date de ieșire

În fişierul de ieşire carmuz.out, pe următoarele $5$ linii se va găsi valoarea $f(s_i, p_i)$, pentru $1 \leq i \leq 5$.

Restricții și precizări

• Notăm cu $S_{len(s)}$ = suma lungimilor șirurilor $s$, iar $S_{len(t)}$ = suma lungimilor șirurilor $t$;
• $1 \leq S_{len(s)}, S_{len(t)} \leq 500 \ 000$;
• Se garantează faptul că $s_i$ și $t_i$ conțin litere mici, pentru $1 \leq i \leq 5$;

Exemplu

carmuz.in

kbkbkg  
bkg  
bbbab  
bbbba  
bbbab  
bbbab  
gkghj  
ggh  
ghgkgjgkg  
gj  

carmuz.out

3  
-1  
0  
1  
4  

Explicație

• Pentru $s = kbkbkg$ și $t = bkg$, putem scoate $[1, 3]$, deci răspunsul este 3.
• Pentru $s = bbbab$ și $t = bbbba$, $t$ nu se regăsește ca subșir, deci răspunsul este -1.
• Pentru $s = bbbab$ și $t = bbbab$, $t$ se regăsește ca subșir, dar nu putem scoate nicio subsecvență, deci răspunsul este 0.