busca.pas

{ COMIENZO DE DESCRIPCION

Dadas dos listas L1,L2 de longitud n1, n2 determinar si la lista L2
contiene una sublista igual a L1, es decir, si existe un conjunto de
indices INDX(1),<INDX(2)<...<INDX(n1) tales que L2(INDX(1)) = L1(1),
L2(INDX(2))=L1(2) .... L2(INDX(n1))=L1(n1). Consigna: escribir una
funcion `function L1,L2 : lista; var INDX: lista): boolean ;' tal que
si L2 contiene a L1 como una sublista, entonces debe retornar `true' y
en `INDX' debe retornar los indices en L2 que componen L1. Si L2 no
contiene a L1 entonces debe retornar `false' e INDX debe estar vacia.
[Tomado en el final del 8-Aug-2003.] keywords: lista

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: busca.pas,v 1.4 2003/07/15 02:39:07 mstorti Exp mstorti $}

program busca_p;

uses u_listpi;

type
  lista	= listpi ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function busca(L1,L2 : lista; var INDX: lista): boolean ;
var
   p1,p2 : posicion;
   i2,e1,e2 : integer;
begin
   INDX.anula;
   p1 := L1.primero;
   p2 := L2.primero;
   i2 :=1;
   { `p1' avanza sobre `L1' }
   { `e1' es el elemento de `L1' en la posicion `p1' }
   { `p2' busca el elemento de `L2' que coincide con `e1' }
   { `i2' es el indice entero (base 1) correspondiente}
   { a `p2' en `L2' }
   while p1<>L1.fin do
   begin
      e1 := L1.recupera(p1);
      while p2<>L2.fin do
      begin
	 e2 := L2.recupera(p2);
	 p2 := L2.siguiente(p2);
	 i2 := i2 +1;
	 if e1=e2 then
	 begin
	    { Encontro el elemento!! }
	    { Inserta el indice en `INDX' y pasa al}
	    { siguiente elemento de `L1'}
	    INDX.inserta(i2-1,INDX.fin);
	    break;
	 end;
      end;
      { Si se termino `L2' y no se termino `L1' entonces}
      { quiere decir que `L2' no coincide con `L1' }
      if (p2=L2.fin) and (p1<>L1.fin) then
      begin
	 INDX.anula;
	 busca := false;
	 exit;
      end;
      p1 := L1.siguiente(p1);
   end;
   busca := true;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   L1, L2, INDX	: Lista;
   k,N,x,M	: integer;
   frac		: real;
begin
   { genera una lista aleatoria }
   L1.anula;
   L2.anula;
   INDX.anula;
   { N es el numero de elementos en L2}
   { Los numeros se generan aleatoriamente entre 0 y M-1 }
   N := 30; M:=10;
   { Generamos L1 de tal tomando aleatoriamente}
   { una fraccion `frac' de los elementos de L2 }
   frac := 0.3;
   
   randomize;
   for k:=1 to N do
   begin
      x := RANDOM(M);
      L2.inserta(x,L2.fin);
      { Aleatoriamente tomamos una fraccion `frac' de}
      { los elementos }
      if random < frac then
	 L1.inserta(x,L1.fin);
      { Con una probabilidad baja insertamos}
      { un elemento que NO esta en L2 de manera que}
      { si este elemento se inserta entonces probablemente}
      { L2 no contenga a L1 y `BUSCA' debe retornar `FALSE' }
      if random < 0.3/N then
      begin
	 x := RANDOM(M);
	 writeln('Inserta elemento extranio ',x);
	 L1.inserta(x,L1.fin);
      end;
   end;

   L1.imprime('L1');
   L2.imprime('L2');
   if busca(L1,L2,INDX) then
   begin
      writeln('L1 contenido en L2 en posiciones');
      INDX.imprime('INDX: ');
   end
   else
      writeln('L1 NO esta contenido en L2');
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}