Se citesc doua siruri de caractere S si T. Determinati, folosind Programarea Dinamica, in cate moduri distincte (dupa pozitii) se poate alege o subsecventa a lui S care sa fie egala cu T.
- Date de intrare
- Pe prima linie se citeste sirul S. Pe a doua linie se citeste sirul T.
- Date de iesire
- Se afiseaza un singur numar: numarul de subsecvente ale lui S egale cu T.
- Restrictii
- 0 <= lungimea S, T <= 1000
Exemple
Exemplul 1
Intrare
rabbbit rabbit
Iesire
3
Exemplul 2
Intrare
babgbag bag
Iesire
5