Caracterele Muzicale

Time limit: 0.07s Memory limit: 144.9MB Input: carmuz.in Output: carmuz.out

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 ss, notăm len(s)len(s) = lungimea șirului ss. Definim [l,r][l, r] din șirul ss = subsecvența de la ll la rr din șirul ss (de exemplu, [3,4][3, 4] din șirul abcdeeabcdee = cdcd).

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

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

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

Spunem că tt se regăsește ca subșir în ss dacă și numai dacă există len(t)len(t) indici 1i1<i2<i3<i4<...<ilen(t)len(s)1 \leq i_1 < i_2 < i_3 < i_4 < ... < i_{len(t)} \leq len(s) astfel încât tj=sijt_j=s_{i_j}, unde 1jlen(t)1 \leq j \leq len(t).

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

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

Pentru exact 55 perechi de șiruri (si,ti)(s_i, t_i), să se afișeze f(si,ti)f(s_i, t_i).

Date de intrare

În fişierul de intrare carmuz.in, pe a 2i2 \cdot i-a linie se găsește șirul sis_i, iar pe a 2i+12 \cdot i + 1-a linie tit_i, pentru 1i51 \leq i \leq 5.

Date de ieșire

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

Restricții și precizări

  • Notăm cu Slen(s)S_{len(s)} = suma lungimilor șirurilor ss, iar Slen(t)S_{len(t)} = suma lungimilor șirurilor tt;
  • 1Slen(s),Slen(t)500 0001 \leq S_{len(s)}, S_{len(t)} \leq 500 \ 000;
  • Se garantează faptul că sis_i și tit_i conțin litere mici, pentru 1i51 \leq i \leq 5;
Nr. Puncte Restricții
1 16 Slen(s),Slen(t)10S_{len(s)}, S_{len(t)} \leq 10
2 18 Slen(s),Slen(t)500S_{len(s)}, S_{len(t)} \leq 500
3 20 len(si)len(ti)+10len(s_i) \leq len(t_i)+10, pentru 1i51 \leq i \leq 5
4 19 Slen(s),Slen(t)5 000S_{len(s)}, S_{len(t)} \leq 5 \ 000
5 27 Fără alte restricții

Exemplu

carmuz.in

kbkbkg  
bkg  
bbbab  
bbbba  
bbbab  
bbbab  
gkghj  
ggh  
ghgkgjgkg  
gj  

carmuz.out

3  
-1  
0  
1  
4  

Explicație

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

Log in or sign up to be able to send submissions!