Se citesc un sir S si un dictionar cu n cuvinte. Determinati, folosind Programarea Dinamica, in cate moduri distincte poate fi impartit S intr-o secventa de cuvinte din dictionar (un cuvant poate fi folosit de oricate ori).
- Date de intrare
- Pe prima linie se citeste sirul S. Pe a doua linie se citeste n. Pe a treia linie se citesc cele n cuvinte ale dictionarului.
- Date de iesire
- Se afiseaza un singur numar: numarul de impartiri posibile.
- Restrictii
- 1 <= lungimea S <= 1000, 1 <= n <= 1000, 1 <= lungimea unui cuvant <= 20
Exemple
Exemplul 1
Intrare
catsanddog 5 cats dog sand and cat
Iesire
2
Exemplul 2
Intrare
aaaaaaa 2 aaaa aaa
Iesire
2