(*

Contact (IOI 1998)
Copyright (C) 2000 Sebastiano Vigna

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



 
Il programma di per se' e` piuttosto banale: dato che i pattern richiesti
sono corti, e` possibile creare un vettore di occorrenze indiciato dal
valore numerico dei pattern. Ci sono pero` numerosi dettagli che possono
indurre in errore: innanzitutto affinche' l'indicizzazione funzioni occorre
prefissare i pattern con 1 (altrimenti 00 e 000 avrebbero lo stesso indice).
Inoltre l'inizio e la fine della stringa di input sono molto rognosi.

*)

{$R+}

Program Contact;

function max(a,b: LongInt): LongInt;
BEGIN
	if a<b then max := b else max := a;
END;

function min(a,b: LongInt): LongInt;
BEGIN
	if b<a then min := b else min := a;
END;


CONST
	MINLUNPATT  = 1;
	MAXLUNPATT = 12;
	NUMPATT = 20;

VAR
	(* Misura le occorrenze dei pattern; il pattern p e` indiciato da 1p
		(cosi`, per esempio, 00 e 000 hanno indici diversi--100 (decimale 8) e
		1000 (decimale 16). *)
	occ: array[0..(1 SHL (MAXLUNPATT+1))-1] of LongInt;
	A, B, N, c, i, j, k, M, t, p, lungh: LongInt;
	ch: Char;
	F: Text;


(* Questa funzione stampa un indice in binario. Prima di tutto cerchiamo il
	bit a uno piu` a sinistra. Quindi lo saltiamo e stampiamo i rimanenti. *)

PROCEDURE stampaindice(n: Integer);
VAR
	i: Integer;

BEGIN
	FOR i:=MAXLUNPATT+1 DOWNTO 0 DO IF ((1 SHL i) AND n <> 0) THEN BREAK;
	WHILE i>0 DO
	BEGIN
		i := i-1;
		IF n AND (1 SHL i) <> 0 THEN WRITE(F, '1') ELSE WRITE(F, '0');
	END;
END;


BEGIN

   ASSIGN(F, '');
	RESET(F);
	READLN(F, A, B, N);

	(* Teniamo traccia della lunghezza letta in lungh per evitare di
		considerare all'inizio pattern inesistenti. *)

   READ(F, ch);

	WHILE ch <> '2' DO
	BEGIN
		c := ord(ch) - ord('0');
		lungh := lungh + 1;

		(* p rappresenta la "finestra" larga B caratteri che attualmente
			vediamo della stringa complessiva. Aggiorniamo p aggiungendo il bit
			c a _destra_. Dobbiamo stare attenti perche' il pattern viene letto
			invece da _sinistra_. Aggiungiamo anche un bit a uno sulla sinistra
			per ottenere l'indice corrispondente al pattern. *)

		p := ((p SHL 1) OR c) AND  (NOT ((NOT 0) SHL B)) OR (1 SHL B);
		t := p;

		(* Dobbiamo ora aggiornare le occorrenze di p e di tutti i pattern di
			lunghezza maggiore o uguale ad A che si ottengono facendo scorrere p
			verso destra. *)

		IF lungh >= B THEN
			FOR i:=A TO B DO
			BEGIN
				occ[t] := occ[t]+1;
				t := t SHR 1;
			END;

		READ(F, ch);
	END;

	(* Quando l'input e` esaurito, abbiamo comunque dentro p diversi pattern
		da leggere: sono quelli che si ottengono eliminando via via un bit a
	   sinistra di p. Si noti che la lunghezza corrente di p e`
		min(B, lungh), e che se lungh < B non e` stato preso ancora in
		considerazione alcun pattern. *)

	FOR i:=min(B, lungh+1)-1 DOWNTO A DO
	BEGIN
		p := p AND (NOT ((NOT 0) SHL i)) OR (1 SHL i);
		t := p;

		FOR j:=A TO i DO
		BEGIN
			occ[t] := occ[t]+1;
			t := t SHR 1;
		END;
	END;

	(* Per estrarre i massimi, non facciamo troppo sforzo: scandiamo il
	vettore occ per trovare il massimo valore, e quindi lo riscandiamo per
	stampare in ordine di valore numerico i vari pattern. Si noti che
	l'indicizzazione che abbiamo scelto fa apparire facilmente nell'ordine
	corretto i pattern: infatti se la stringa s e` piu` lunga della stringa
	t il suo indice e` maggiore, dato che contiene un 1 in una posizione piu`
	a sinistra, e se s e t hanno la stessa lunghezza sono ordinate sulla base
	del loro valore numerico. *)

	ASSIGN(F, '');
	REWRITE(F);

	REPEAT
		M := Low(M);

		(* Troviamo il massimo delle occorrenze *)
		FOR i:=0 TO (1 SHL (B+1))-1 DO M := max(M, occ[i]);

		(* Dobbiamo stampare solo pattern che sono comparsi qualche volta. *)
		if M = 0 THEN BREAK;

		WRITE(F, M);

		FOR i:=(1 SHL (B+1))-1 DOWNTO 0 DO (* Questa volta dobbiamo scandire il
															vettore in ordine inverso. *)
			IF occ[i] = M THEN
			BEGIN
				WRITE(F, ' ');
				stampaindice(i);
				occ[i] := 0; (* Ogni volta che stampiamo una stringa mettiamo a
									zero il suo numero di occorrenze, in modo da non
									riconsiderarla. *)
			END;

		WRITELN(F);
		N := N-1;
	UNTIL N = 0;
END.