Programozás‎ > ‎Feladatok‎ > ‎

Leghosszabb kezdőszelet

Bizonyos biológiai objektumok szerkezete az összetevők sorozatával írható le, ahol minden rész egy nagybetűvel jelölhető. A biológusok egyik feladata, hogy a hosszú sorozatokat rövidebb részekre, úgynevezett primitívekre bontsák.

Akkor mondjuk, hogy az S sorozat felbontható P-beli primitívekre, ha kiválaszthatók primitívek P-ből úgy, hogy ezek egymás után fűzésével megkapjuk az S sorozatot. Egy primitív többször is használható, és nem kell mindet felhasználni. Például az ABABACABAAB sorozat felbontható P= {A, AB, BA, CA, BBC}-beli primitívekre. 

Az S első K karaktere az S K hosszú kezdőszelete. 

Feladat

Írjunk programot, ami megadja, hogy milyen hosszú az S leghosszabb kezdőszelete, ami előállítható P-beli primitívekből.

Bemenet

A a primitívek felsorolásával kezdődik. A primitívek több sorban, szóközzel elválasztva vannak megadva. Legfeljebb 200 primitív lehet, és hosszuk 1 és 10 közé esik.
A primitívek felsorolását egy olyan sor zárja, ami egyetlen '.' karaktert tartalmaz. Végül S kódolása következik: soronként legfeljebb 76 karakter, összesen legfeljebb 200000 karakter. Az sorvége karakterek ("newlines") nem tartoznak S-hez.

Kimenet

Egyetlen egész, a P-beli primitívekből előállítható leghosszabb kezdőszelet hossza.

Példa

Bemenet  Kimenet
A AB BA CA BBC
.
ABABACABAABC		11

Tesztadatok

Címkék

A feladat forrása: USACO training material, Longest Prefix
Algoritmusok: 

megoldás