Anumite structuri biologice pot fi reprezentate prin secvente de constituenti.
Constituentii sunt notati cu litere mari. Biologii sunt interesati în
descompunerea unei secvente lungi în altele mai scurte, denumite primitive.
Spunem ca o secventa S poate fi compusa dintr-o multime data P de primitive,
daca exista n primitive p1, p2, ..., pn în P astfel încât
S sa se obtina prin concatenarea lor. Aceeasi primitiva poate aparea în
concatenare de mai multe ori sau poate lipsi. De exemplu, secventa ABABACABAAB poate fi obtinuta din multimea de primitive {A, AB, BA, CA, BBC}.
Primele K caractere ale unei secvente S constituie prefixul lui S de lungime
K.
Cerinta
Scrieti un program care accepta la intrare un set P de primitive si o secventa
T formata din constituenti. Programul trebuie sa calculeze lungimea celui mai
lung prefix al secventei T care poate fi obtinut cu primitive din P.
Date de intrare
Fisierul de intrare prefix.in
contine pe prima linie numarul natural N, care reprezinta numarul de primitive din
P (1<=N<=20). Urmatoarele 2*N linii contin primitivele. Pentru fiecare primitiva sunt scrise
doua linii: pe prima linie este lungimea primitivei, iar pe urmatoarea o succesiune
de maxim 20 litere mari, care reprezinta primitiva. Cele N primitive sunt distincte. Pe urmatoarele linii se afla secventa de examinat, cate un caracter pe o linie.
Secventa contine maxim 500000 litere mari, sfârsitul secventei fiind marcat
de aparitia caracterului punct.
Date de iesire
In fisierul de iesire prefix.out
se va scrie o singura linie pe care se afla lungimea celui mai lung prefix al
lui T care poate fi format din elemente ale multimii P.
Exemple
prefix.in
prefix.out
5
1 A
2 AB
3 BBC
2 CA
2 BA
A
B
A
B
A
C
A
B
A
A
B
C
.