Codici nascosti (codes)

Vengono dati un insieme di parole ed un testo. Il testo contiene un messaggio composto da parole (inserite nel testo in modo particolare ed eventualmente ambiguo).

Le parole e il testo sono sequenze di lettere maiuscole e minuscole dell'alfabeto inglese. C'è differenza tra lettere minuscole e maiuscole. La lunghezza di una parola è calcolata nel solito modo: per esempio, la parola CON ha lunghezza 3.

Le lettere di una parola non devono apparire consecutivamente nel testo. Per esempio, se la parola CON è presente nel testo, sarà sempre nella forma CuOvN dove u e v indicano sequenze arbitrarie di lettere (e quindi, eventualmente, vuote). Diremo che CuOvN è una copertura per CON. In generale, una copertura per una parola è una sottosequenza del testo per cui la prima e l'ultima lettera della sottosequenza sono uguali, rispettivamente, alla prima e all'ultima lettera della parola ed è possibile ottenere la parola cancellando alcune (o nessuna) lettere della sottosequenza. Una parola può capitare in una o più coperture o può non essere presente affatto nel testo, e una copertura può coprire più di una parola.

Una copertura è identificata dalla sua posizione iniziale (posizione della sua prima lettera) e dalla sua posizione finale (posizione della sua ultima lettera) nel testo. La prima lettera del testo è in posizione 1. Diciamo che due coperture C₁ e C₂ non si sovrappongono se la posizione finale di C₁ è minore della posizione iniziale di C₂ e viceversa.

Per trovare una soluzione è necessario estrarre il messaggio nascosto nel testo. Una soluzione è un insieme di elementi, ognuno dei quali è formato da una parola e da una copertura per quella parola, in modo che le seguenti condizioni siano tutte soddisfatte:

• le coperture non si sovrappongono una all'altra;
• ogni copertura non supera 1000 lettere di lunghezza;
• la somma delle lunghezze delle parole è massima (ogni elemento contribuisce alla somma con la lunghezza della parola che contiene).

Nel caso ci siano più soluzioni è necessario darne in output una sola.

Dati in input

Ci sono due file di input: words.inp e text.inp. Il file words.inp contiene la lista di parole e text.inp contiene il testo.

• La prima linea di words.inp contiene il valore di N. Ognuna delle N linee successive contiene una parola: una sequenza di lettere non interrota da altri caratteri. Le parole sono identificate dal loro ordine di apparizione nel file: gli interi da 1 a N sono gli identificatori delle parole.
• Il file text.inp è formato da una sequenza di lettere (terminata da due caratteri: End-of-Line seguito da End-of-File). Il file non contiene altri caratteri.

Dati in output

Il file di output si chiamerà codes.out.

• La prima linea conterrà la somma ottenuta dalla soluzione.
• Ognuna delle linee seguenti indicherà un elemento della soluzione; ogni linea sarà composta da tre interi i, s e e: i è l'identificatore della parola nascosta nella copertura che ha come posizione iniziale s e come posizione finale e. L'ordine delle linee che seguono la prima non è importante.

Vincoli

• 1 ≤ N ≤ 100, dove N è il numero di parole;
• la massima lunghezza di una parola è di 100 lettere;
• 1 ≤ numero di lettere del testo ≤ 1000000 (un milione);
• diciamo che una copertura C per una parola P è minimale a destra se nessun prefisso proprio di C (un prefisso proprio di C è una sottosequenza iniziale di C non uguale a C) è una copertura per P. Per esempio CCOON è una copertura minimale a destra per CON, mentre CCOONON non lo è.

  È garantito che nel testo:

  • per ogni posizione il numero di coperture minimali a destra comprendenti quella posizione non supera 2500;
  • il numero di coperture minimali a destra non supera 10000.

Esempio

4
RuN
RaBbit
HoBbit
StoP

StXRuYNvRuHoaBbvizXztNwRRuuNNP

12
2 9 21
1 4 7
1 24 28

Il messaggio della soluzione è "RuN RaBbit RuN"; un'altra soluzione sarebbe potuta essere "Run HoBbit Run".