/*

Hidden Codes (IOI 1999)
Copyright (C) 2002 Flavio Chierichetti

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

The Idea Behind:

L'algoritmo č diviso in due parti fondamentali: la ricerca delle coperture
minime e la programmazione dinamica che sceglie l'insieme pių redditizio di
esse.


Ricerca Coperture Minime

Una copertura minima per una parola non contiene sottosequenze strette (una
sottosequenza stretta di S č una sottosequenza di S diversa da S) valide come
coperture per quella parola.

Nello scrivere il programma č stato tenuto conto del fatto che alle IOI del '99
era usato un simil-OS che non permetteva di allocare il milione di byte
necessario per mantenere in memoria tutto il testo: il testo č quindi caricato
a "pezzi" di LSeq caratteri per volta.

Per ogni carattere del testo e per ogni parola si guardando al pių gli LSeq-1
caratteri successivi cercando una copertura per quella parola. Ci si ferma
appena si trova una copertura: le coperture cosė trovate saranno sicuramente
destra-minimali.

Si controlla poi se nelle coperture fino a quel momento trovate ce n'č una che
copra la stessa parola e che abbia la stessa posizione finale di quella appena
trovata. Se č cosė abbiamo trovato una riduzione di quella copertura e la
modifichiamo. Altrimenti aggiungiamo la copertura al vettore.

Alla fine di questo procedimento avremo tutte le coperture minime (le coperture
sinistra-minimali di quelle destra-minimali).


Programmazione Dinamica

1) Si ordina il vettore delle coperture per l'inizio di ogni copertura in ordine
crescente.

2) Per ogni copertura i si scandiscono tutte le coperture j che iniziano prima di
i.

3) Si sceglie quella quella con Sum[j] maggiore e si pone Sum[i] = Sum[j] +
Lunghezza della parola della copertura i.

4) Alla fine si ricerca in Sum il valore maggiore e si da in output.  (C'č anche
un altro vettore per sapere quali coperture si sono usate)

*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

enum { 
  NWord = 100,  /* Massimo numero di parole */
  LWord = 100,  /* Massima lunghezza di una parola */
  NSeq = 10000, /* Massimo numero coperture destra-minimali */
  LSeq = 1000   /* Massima lunghezza copertura */
};

typedef struct {
  int i;        /* Identificatore della parola */
  long s, e;    /* Inizio, fine copertura */
} cover;

void getMinSeq();
int cmp(const void *a, const void *b);

/*
  W: Numero di parole
  S: Numero di coperture minime
  Length[i]: Lunghezza parola i-esima
  Word[i]: Parola i-esima  
  TextChunk: Buffer per l'input del testo
  Seq[i]: copertura minima i-esima
  Sum[i]: massimo valore ottenibile arrivando fino all'i-esima copertura
  Prec[i]: indice precedente copertura nella realizzazione di Sum[i]
*/

int W, S, Length[NWord];
char Word[NWord][LWord + 1], TextChunk[LSeq];

cover Seq[NSeq];
int Sum[NSeq], Prec[NSeq];

int main(int argc, char *argv[]) {
  FILE *f;
  int i, j;

  /* Lettura parole */
  f = fopen("words.inp", "r");

  fscanf(f, " %d", &W);
  for ( i = 0 ; i < W ; i++ ) {
    fscanf(f, " %s", Word[i]);
    Length[i] = strlen(Word[i]);
  }

  fclose(f);

  /* Ricerca coperture minime */
  getMinSeq();

  qsort(Seq, S, sizeof(cover), cmp);

  /* Ricerca migliore soluzione */
  for ( i = 0 ; i < S ; i++ ) {
    Sum[i] = 0;
    Prec[i] = -1;

    for ( j = 0 ; Seq[j].s < Seq[i].s ; j++ )
      if ( Seq[j].e < Seq[i].s && Sum[j] > Sum[i] ) {
	Sum[i] = Sum[j];
	Prec[i] = j;
      }

    Sum[i] += Length[Seq[i].i - 1];
  }

  j = 0;
  for ( i = 1 ; i < S ; i++ )
    if ( Sum[i] > Sum[j] )
      j = i;

  f = fopen("codes.out", "w");

  /* Stampa soluzione */
  fprintf(f, "%d\n", Sum[j]);

  for ( i = j ; i != -1 ; i = Prec[i] )
    fprintf(f, "%d %d %d\n", Seq[i].i, Seq[i].s, Seq[i].e);

  fclose(f);

  return 0;
}

void getMinSeq() {
  FILE *f;
  long s;
  int n, i, j, e;

  f = fopen("text.inp", "r");

  /* Riempimento del buffer di al pių LSeq elementi */
  for ( e = 0 ; e < LSeq ; e++ )
    if ( fscanf(f, " %c", TextChunk + e) != 1 )
      break;
  
  /* Ricerca coperture minime */
  for ( s = 0 ; e > 0 ; e--, s++ ) {
    for ( n = 0 ; n < W ; n++ )
      if ( Word[n][0] == TextChunk[0] ) { 

	j = 0;
	for ( i = 0 ; i < e ; i++ )
	  if ( Word[n][j] == TextChunk[i] ) {
	    j++;

	    if ( j == Length[n] )
	      break;
	  }

	if ( j == Length[n] ) {
	  for ( j = 0 ; j < S ; j++ )
	    if ( Seq[j].i == n + 1 && Seq[j].e == s + i + 1 )
	      break;

	  Seq[j].i = n + 1;
	  Seq[j].s = s + 1;
	  Seq[j].e = s + i + 1;

	  if ( j == S )
	    S++;
	}
      }
    
    /* Shift del buffer */
    for ( i = 1 ; i < e ; i++ )
      TextChunk[i-1] = TextChunk[i];

    if ( fscanf(f, " %c", TextChunk + e - 1) == 1 )
      e++;
  }

  fclose(f);
}

int cmp(const void *a, const void *b) {
  return ((cover*)a)->s - ((cover*)b)->s;
}