02. Trazenje podslike/XDS/PODSLIKA.MOD

   1 MODULE Podslika;
   2
   3   FROM FIO IMPORT
   4     File, Open, Close, RdCard, EOF, Exists;
   5   FROM IO IMPORT
   6     WrLn, WrStr, WrCard;
   7
   8   CONST
   9     MaxDim = 100;
  10     BrojBoja = 16;
  11     Osnova = MaxDim * (BrojBoja - 1) + 1;
  12     ProstBroj = 3001;
  13     ImeVel = 'Velika.Sli';
  14     ImeMal = 'Mala.Sli';
  15
  16   TYPE
  17
  18     Slika = ARRAY [1 .. MaxDim], [1 .. MaxDim] OF CARDINAL;
  19
  20   VAR
  21     Velika, Mala: Slika;
  22     DimVel, DimMal, Vr, Ko: CARDINAL;
  23     KljucMale, KljucSegmenta, Stepen: CARDINAL;
  24     Ok, Iste: BOOLEAN;
  25
  26   PROCEDURE Citaj(VAR Slika: Slika;
  27                   Ime: ARRAY OF CHAR;
  28                   VAR Dim: CARDINAL;
  29                   VAR Ok: BOOLEAN);
  30     VAR
  31       F: File;
  32       Vr, Ko: CARDINAL;
  33       Jos: BOOLEAN;
  34   BEGIN
  35     Ok:= Ok AND Exists(Ime);
  36     IF Ok THEN
  37       F:= Open(Ime);
  38       Dim:= RdCard(F);
  39       Vr:= 1;
  40       Jos:= TRUE;
  41       WHILE Jos AND (Vr <= Dim) DO
  42         Ko:= 1;
  43         WHILE Jos AND (Ko <= Dim) DO
  44           Slika[Vr, Ko]:= RdCard(F);
  45           Ok:= Ok AND (Slika[Vr, Ko] < BrojBoja);
  46           Jos:= Ok AND NOT EOF;
  47           INC(Ko);
  48         END;
  49         INC(Vr);
  50       END;
  51       Close(F);
  52     ELSE
  53       Dim:= 0;
  54     END;
  55   END Citaj;
  56
  57   PROCEDURE Proveri(VAR Velika, Mala: Slika;
  58                     DimMal, Vr, Ko: CARDINAL): BOOLEAN;
  59     VAR
  60       i, j: CARDINAL;
  61       Iste: BOOLEAN;
  62   BEGIN
  63     Iste:= TRUE;
  64     i:= 1;
  65     WHILE Iste AND (i <= DimMal) DO
  66       j:= 1;
  67       WHILE Iste AND (j <= DimMal) DO
  68         IF Mala[i, j] # Velika[Vr + i - 1, Ko + j - 1] THEN
  69           Iste:= FALSE;
  70         END;
  71         INC(j);
  72       END;
  73       INC(i);
  74     END;
  75     RETURN Iste;
  76   END Proveri;
  77
  78   PROCEDURE Hash(S: Slika; DimMal, Vr: CARDINAL): CARDINAL;
  79     VAR
  80       i, j: CARDINAL;
  81       Kljuc, ZbirKolone, Temp: CARDINAL;
  82   BEGIN
  83
  84     Stepen:= 1;
  85     Kljuc:= 0;
  86
  87     FOR i:= DimMal TO 1 BY -1 DO
  88
  89       ZbirKolone:= 0;
  90       FOR j:= Vr TO Vr + DimMal - 1 DO
  91         ZbirKolone:= ZbirKolone + (S[j, i]);
  92       END;
  93
  94       Temp:= (ZbirKolone * Stepen) MOD ProstBroj;
  95       Kljuc:= (Kljuc + Temp) MOD ProstBroj;
  96       Stepen:= (Stepen * Osnova) MOD ProstBroj;
  97
  98     END;
  99
 100     Stepen:= Stepen DIV Osnova;
 101
 102     RETURN Kljuc;
 103
 104   END Hash;
 105
 106   PROCEDURE DoterajHash(S: Slika; DimMal, Vr, Ko: CARDINAL;
 107                         VAR Kljuc: CARDINAL);
 108     VAR
 109       j: CARDINAL;
 110       ZbirKolone, Temp: CARDINAL;
 111   BEGIN
 112
 113     ZbirKolone:= 0;
 114     FOR j:= Vr TO Vr + DimMal - 1 DO
 115       ZbirKolone:= ZbirKolone + (S[j, Ko - 1]);
 116     END;
 117
 118     Temp:= (ZbirKolone * Stepen) MOD ProstBroj;
 119
 120     IF Kljuc >= Temp THEN
 121       Kljuc:= Kljuc - Temp;
 122     ELSE
 123       Kljuc:= Kljuc + ProstBroj - Temp;
 124     END;
 125
 126     Kljuc:= (Kljuc * Osnova) MOD ProstBroj;
 127
 128     ZbirKolone:= 0;
 129     FOR j:= Vr TO Vr + DimMal - 1 DO
 130       ZbirKolone:= ZbirKolone + (S[j, Ko + DimMal - 1]);
 131     END;
 132
 133     Kljuc:= (Kljuc + ZbirKolone) MOD ProstBroj;
 134
 135   END DoterajHash;
 136
 137 BEGIN
 138   Ok:= TRUE;
 139   Citaj(Velika, ImeVel, DimVel, Ok);
 140   Citaj(Mala, ImeMal, DimMal, Ok);
 141   IF Ok THEN
 142     KljucMale:= Hash(Mala, DimMal, 1);
 143     FOR Vr:= 1 TO (DimVel - DimMal + 1) DO
 144       KljucSegmenta:= Hash(Velika, DimMal, Vr);
 145       IF (KljucMale = KljucSegmenta) THEN
 146         Iste:= Proveri(Velika, Mala, DimMal, Vr, 1);
 147         IF Iste THEN
 148           WrLn;
 149           WrStr('Podslika je nadjena. Pocinje na poziciji (');
 150           WrCard(Vr, 1); WrStr(', '); WrCard(1, 1); WrStr(')');
 151         END;
 152       END;
 153       FOR Ko:= 2 TO (DimVel - DimMal + 1) DO
 154         DoterajHash(Velika, DimMal, Vr, Ko, KljucSegmenta);
 155         IF (KljucMale = KljucSegmenta) THEN
 156           Iste:= Proveri(Velika, Mala, DimMal, Vr, Ko);
 157           IF Iste THEN
 158             WrLn;
 159             WrStr('Podslika je nadjena. Pocinje na poziciji (');
 160             WrCard(Vr, 1); WrStr(', '); WrCard(Ko, 1); WrStr(')');
 161           END;
 162         END;
 163       END;
 164     END;
 165   ELSE
 166     WrStr('Greska u citanju fajla.');
 167   END;
 168 END Podslika.