X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-teorijske-vezbe.git;a=blobdiff_plain;f=02.%20Trazenje%20podslike%2FTopSpeed%2FPODSLIKA.MOD;fp=02.%20Trazenje%20podslike%2FTopSpeed%2FPODSLIKA.MOD;h=78dc19b82e88c252f91c69f22667015709b0e8f4;hp=0000000000000000000000000000000000000000;hb=f3e39a2dfd9a49f7c5516526ddd17f0ea40b07cc;hpb=bcfa13cb2167d46a110fe6aa3d8e4ef541b37a2e

diff --git a/02. Trazenje podslike/TopSpeed/PODSLIKA.MOD b/02. Trazenje podslike/TopSpeed/PODSLIKA.MOD
new file mode 100644
index 0000000..78dc19b
--- /dev/null
+++ b/02. Trazenje podslike/TopSpeed/PODSLIKA.MOD	
@@ -0,0 +1,168 @@
+MODULE Podslika;
+
+  FROM FIO IMPORT
+    File, Open, Close, RdCard, EOF, OK, Exists;
+  FROM IO IMPORT
+    WrLn, WrStr, WrCard;
+
+  CONST
+    MaxDim = 100;
+    BrojBoja = 16;
+    Osnova = MaxDim * (BrojBoja - 1) + 1;
+    ProstBroj = 3001;
+    ImeVel = 'Velika.Sli';
+    ImeMal = 'Mala.Sli';
+
+  TYPE
+    Boja = [0 .. BrojBoja - 1];
+    Slika = ARRAY [1 .. MaxDim], [1 .. MaxDim] OF Boja;
+
+  VAR
+    Velika, Mala: Slika;
+    DimVel, DimMal, Vr, Ko: CARDINAL;
+    KljucMale, KljucSegmenta, Stepen: LONGCARD;
+    Ok, Iste: BOOLEAN;
+
+  PROCEDURE Citaj(VAR Slika: Slika;
+                  Ime: ARRAY OF CHAR;
+                  VAR Dim: CARDINAL;
+                  VAR Ok: BOOLEAN);
+    VAR
+      F: File;
+      Vr, Ko: CARDINAL;
+      Jos: BOOLEAN;
+  BEGIN
+    Ok:= Ok AND Exists(Ime);
+    IF Ok THEN
+      F:= Open(Ime);
+      Dim:= RdCard(F);
+      Vr:= 1;
+      Jos:= TRUE;
+      WHILE Jos AND (Vr <= Dim) DO
+        Ko:= 1;
+        WHILE Jos AND (Ko <= Dim) DO
+          Slika[Vr, Ko]:= RdCard(F);
+          Ok:= Ok AND (Slika[Vr, Ko] < BrojBoja);
+          Jos:= Ok AND NOT EOF;
+          INC(Ko);
+        END;
+        INC(Vr);
+      END;
+      Close(F);
+    ELSE
+      Dim:= 0;
+    END;
+  END Citaj;
+
+  PROCEDURE Proveri(VAR Velika, Mala: Slika;
+                    DimMal, Vr, Ko: CARDINAL): BOOLEAN;
+    VAR
+      i, j: CARDINAL;
+      Iste: BOOLEAN;
+  BEGIN
+    Iste:= TRUE;
+    i:= 1;
+    WHILE Iste AND (i <= DimMal) DO
+      j:= 1;
+      WHILE Iste AND (j <= DimMal) DO
+        IF Mala[i, j] # Velika[Vr + i - 1, Ko + j - 1] THEN
+          Iste:= FALSE;
+        END;
+        INC(j);
+      END;
+      INC(i);
+    END;
+    RETURN Iste;
+  END Proveri;
+
+  PROCEDURE Hash(S: Slika; DimMal, Vr: CARDINAL): LONGCARD;
+    VAR
+      i, j: CARDINAL;
+      Kljuc, ZbirKolone, Temp: LONGCARD;
+  BEGIN
+
+    Stepen:= 1;
+    Kljuc:= 0;
+
+    FOR i:= DimMal TO 1 BY -1 DO
+
+      ZbirKolone:= 0;
+      FOR j:= Vr TO Vr + DimMal - 1 DO
+        ZbirKolone:= ZbirKolone + LONGCARD(S[j, i]);
+      END;
+
+      Temp:= (ZbirKolone * Stepen) MOD ProstBroj;
+      Kljuc:= (Kljuc + Temp) MOD ProstBroj;
+      Stepen:= (Stepen * Osnova) MOD ProstBroj;
+
+    END;
+
+    Stepen:= Stepen DIV Osnova;
+
+    RETURN Kljuc;
+
+  END Hash;
+
+  PROCEDURE DoterajHash(S: Slika; DimMal, Vr, Ko: CARDINAL;
+                        VAR Kljuc: LONGCARD);
+    VAR
+      i, j: CARDINAL;
+      ZbirKolone, Temp: LONGCARD;
+  BEGIN
+
+    ZbirKolone:= 0;
+    FOR j:= Vr TO Vr + DimMal - 1 DO
+      ZbirKolone:= ZbirKolone + LONGCARD(S[j, Ko - 1]);
+    END;
+
+    Temp:= (ZbirKolone * Stepen) MOD ProstBroj;
+
+    IF Kljuc >= Temp THEN
+      Kljuc:= Kljuc - Temp;
+    ELSE
+      Kljuc:= Kljuc + ProstBroj - Temp;
+    END;
+
+    Kljuc:= (Kljuc * Osnova) MOD ProstBroj;
+
+    ZbirKolone:= 0;
+    FOR j:= Vr TO Vr + DimMal - 1 DO
+      ZbirKolone:= ZbirKolone + LONGCARD(S[j, Ko + DimMal - 1]);
+    END;
+
+    Kljuc:= (Kljuc + ZbirKolone) MOD ProstBroj;
+
+  END DoterajHash;
+
+BEGIN
+  Ok:= TRUE;
+  Citaj(Velika, ImeVel, DimVel, Ok);
+  Citaj(Mala, ImeMal, DimMal, Ok);
+  IF Ok THEN
+    KljucMale:= Hash(Mala, DimMal, 1);
+    FOR Vr:= 1 TO (DimVel - DimMal + 1) DO
+      KljucSegmenta:= Hash(Velika, DimMal, Vr);
+      IF (KljucMale = KljucSegmenta) THEN
+        Iste:= Proveri(Velika, Mala, DimMal, Vr, 1);
+        IF Iste THEN
+          WrLn;
+          WrStr('Podslika je nadjena. Pocinje na poziciji (');
+          WrCard(Vr, 1); WrStr(', '); WrCard(1, 1); WrStr(')');
+        END;
+      END;
+      FOR Ko:= 2 TO (DimVel - DimMal + 1) DO
+        DoterajHash(Velika, DimMal, Vr, Ko, KljucSegmenta);
+        IF (KljucMale = KljucSegmenta) THEN
+          Iste:= Proveri(Velika, Mala, DimMal, Vr, Ko);
+          IF Iste THEN
+            WrLn;
+            WrStr('Podslika je nadjena. Pocinje na poziciji (');
+            WrCard(Vr, 1); WrStr(', '); WrCard(Ko, 1); WrStr(')');
+          END;
+        END;
+      END;
+    END;
+  ELSE
+    WrStr('Greska u citanju fajla.');
+  END;
+END Podslika.