Se consideră un text format numai din litere mici şi N cuvinte formate de asemenea numai din litere mici. Oricare două cuvinte se pot combina prin întrepătrunderea literelor lor, dar fără a schimba ordinea literelor. De exemplu, abc şi xyzt pot obţine prin combinare abcxyzt sau abxcyzt sau xaybczt, dar nu se poate obţine axbczyt, deoarece y trebuia să apară înaintea lui z, aşa cum este iniţial în xyzt.
Cerinţă
Scrieţi un program care să verifice numărul perechilor de cuvinte din cele N date iniţial care obţin prin combinare o subsecvenţă a textului.
Date de intrare
Fisierul de intrare combcuv.in conţine pe prima linie textul, pe a doua linie un număr natural N, iar pe următoarele N linii se află câte un cuvânt.
Date de ieşire
Fisierul de iesire combcuv.out va conţine un singur număr natural reprezentând numărul de perechi de cuvinte care prin combinare obţin o subsecvenţă a textului.
Restricţii
Textul conţine cel mult 200 de litere mici; textul nu conţine spaţii.
Orice cuvânt conţine cel puţin o literă şi cel mult 30
2 <= N <= 100
Exemple
combcuv.in
combcuv.out
Explicaţii
faacbtbacabb
5
abac
acbta
bt
cb
atcb
2
Textul este faacbtbacabb şi sunt 5 cuvinte.
Combinând perechea de cuvinte (abac, acbta) putem obţine aacbtbaca, care este subsecvenţă a textului.
Combinând perechea de cuvinte (bt, cb) putem obţine cbtb, care este subsecvenţă a textului.
De remarcat că perechea (abac, atcb) nu poate obţine prin combinare subsecvenţa aacbtbac.