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 |