DDD'97 Opgave 2 PREFIX

Strukturen for visse biologiske objekter repræsenteres ved en sekvens af deres "byggesten". Disse byggesten repræsenteres ved store bogstaver.

Biologer er interesserede i at opdele en lang sekvens i kortere. Disse korte sekvenser kaldes for primitiver. Sekvensen S kan opbygges fra en given mængde P af primitiver, hvis der findes n primitiver p₁ , ... , p_n i P , således at konkatenationen p₁ ... p_n af disse primitiver er lig med S . At konkatenere primitiverne p₁ , ... , p_n betyder at sætte dem efter hinanden uden mellemrum og i den givne rækkefølge. Et primitiv kan forekomme mere end én gang i konkatenationen, og ikke alle primitiver behøver at forekomme.

F.eks. kan ABABACABAAB opbygges fra følgende mængde af primitiver

De første K bogstaver fra en sekvens kaldes her et prefix . Det har længden K .

Skriv et program, som indlæser en mængde P af primitiver og en sekvens T af byggesten. Programmet skal beregne længden af det længste prefix for T som kan opbygges ved hjælp af primitiverne fra P .

Input data

Der er to input-filer.

Filen INPUT.TXT beskriver mængden P af primitiver, og filen DATA.TXT indeholder den sekvens T , som skal undersøges.

Den første linje i filen INPUT.TXT indeholder tallet N , som er antallet af primitiver i P (1 £ N £ 100) . Derefter beskrives primitiverne, hvert af dem i to på hinanden følgende linjer. Den første af disse linjer indeholder tallet L som er længden af primitivet (1 £ L £ 20) . Den anden af disse linjer indeholder en streng af store bogstaver ('A' til 'Z') af længden L . De N primitiver er alle forskellige.

Hver linje i DATA.TXT indeholder eet stort bogstav på første plads. Denne fil afsluttes med en linje som kun indeholder et punktum. Sekvensens længde er mindst 1 og højst 500.000 .

Output data

Den første linje i filen OUTPUT.TXT skal indeholde længden af det længste prefix for T som kan opbygges fra mængden P .

Eksempel på input og output

Den følgende figur viser et muligt sæt input-filer og den tilsvarende output-fil.

INPUT.TXT	DATA.TXT	OUTPUT.TXT
5	A	11
1	B
A	A
2	B
AB	A
3	C
BBC	A
2	B
CA	A
2	A
BA	B
	C
	B
	.