Selecție CPPI 2024 - Mirror Juniori | Diff

Cerință

Ana și Maria au primit, fiecare, câte un șir de caractere format doar din litere mici. Notăm cu $S_1$ șirul Anei și cu $S_2$ șirul Mariei. Acum, cele două și-au propus să șteargă anumite litere din $S_1$ și $S_2$ până când vor obține două șiruri identice. Pentru aceasta, Ana poate să șteargă caractere doar de la începutul și finalul șirului său, rezultând în final o subsecvență continuă din $S_1$. Maria poate să șteargă orice caractere din $S_2$, putând obține un subșir al șirului său inițial.

Să se calculeze lungimea maximă a șirului pe care l-ar putea obține cele două fete.

Date de intrare

Prima linie a fișierului diff.in conține șirul $S_1$ iar a doua linie conține șirul $S_2$.

Date de ieșire

Pe prima linie a fișierului diff.out se află lugimea maximă a șirului final obținut de cele două fete.

Restricții și precizări

• $S_1$ și $S_2$ conțin doar litere mici ale alfabetului.
• Lungimile șirurilor date sunt cuprinse între $1$ și $2 \ 000$ inclusiv.
• Pentru $37$ de puncte, lungimile șirurilor vor fi cuprinse între $1$ și $200$ inclusiv.

Exemplu

diff.in

fabcmxyztt
yabcnmnxyz

diff.out

7

Explicație

• fabcmxyztt
• yabcnmnxyz
  Cel mai mare șir pe care îl pot obține cele două fete este abcmxyz.