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 , notăm = lungimea șirului . Definim din șirul = subsecvența de la la din șirul (de exemplu, din șirul = ).
Definim , unde și sunt două șiruri de caractere astfel:
- Dacă nu se regăsește ca subșir în , ;
- Altfel, = lungimea maximă a unei subsecvențe pe care o putem scoate din astfel încât să se regăsească ca subșir în în continuare.
Dacă scoatem subsecvența din , va deveni:
Spunem că se regăsește ca subșir în dacă și numai dacă există indici astfel încât , unde .
De exemplu, pentru și , , deoarece putem scoate subsecvența din , acesta devenind , iar se regăsește ca subșir.
Pentru și , , deoarece nu se regăseşte ca subşir în .
Pentru exact perechi de șiruri , să se afișeze .
Date de intrare
În fişierul de intrare carmuz.in
, pe a -a linie se găsește șirul , iar pe a -a linie , pentru .
Date de ieșire
În fişierul de ieşire carmuz.out
, pe următoarele linii se va găsi valoarea , pentru .
Restricții și precizări
- Notăm cu = suma lungimilor șirurilor , iar = suma lungimilor șirurilor ;
- ;
- Se garantează faptul că și conțin litere mici, pentru ;
Nr. | Puncte | Restricții |
---|---|---|
1 | 16 | |
2 | 18 | |
3 | 20 | , pentru |
4 | 19 | |
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 și , putem scoate , deci răspunsul este 3.
- Pentru și , nu se regăsește ca subșir, deci răspunsul este -1.
- Pentru și , se regăsește ca subșir, dar nu putem scoate nicio subsecvență, deci răspunsul este 0.