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 p1 , ... , pn i P , således at konkatenationen p1 ... pn af disse primitiver er lig med S . At konkatenere primitiverne p1 , ... , pn 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

{ A, AB, BA, CA, BBC } .

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 £ £ 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 £ £ 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
5A11
1B
AA
2B
ABA
3C
BBCA
2B
CAA
2A
BAB
C
B
.