From: Doni Pracner Date: Wed, 30 Oct 2013 14:23:34 +0000 (+0100) Subject: 02 - zapravo se zove Trazenje podslike X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-teorijske-vezbe.git;a=commitdiff_plain;h=f3e39a2dfd9a49f7c5516526ddd17f0ea40b07cc 02 - zapravo se zove Trazenje podslike --- diff --git a/02. Podslika/Prezentacija.ppt b/02. Podslika/Prezentacija.ppt deleted file mode 100644 index 0c685f2..0000000 Binary files a/02. Podslika/Prezentacija.ppt and /dev/null differ diff --git a/02. Podslika/TopSpeed/MALA.SLI b/02. Podslika/TopSpeed/MALA.SLI deleted file mode 100644 index a05cae8..0000000 --- a/02. Podslika/TopSpeed/MALA.SLI +++ /dev/null @@ -1,6 +0,0 @@ -5 - 0 0 1 0 0 - 0 1 1 1 0 - 1 1 2 1 1 - 0 1 1 1 0 - 0 0 1 0 0 diff --git a/02. Podslika/TopSpeed/PODSLIKA.MOD b/02. Podslika/TopSpeed/PODSLIKA.MOD deleted file mode 100644 index 78dc19b..0000000 --- a/02. Podslika/TopSpeed/PODSLIKA.MOD +++ /dev/null @@ -1,168 +0,0 @@ -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. diff --git a/02. Podslika/TopSpeed/VELIKA.SLI b/02. Podslika/TopSpeed/VELIKA.SLI deleted file mode 100644 index 050166c..0000000 --- a/02. Podslika/TopSpeed/VELIKA.SLI +++ /dev/null @@ -1,13 +0,0 @@ -12 - 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 1 0 0 0 0 0 0 0 0 - 0 0 1 1 1 0 0 0 0 0 0 0 - 0 1 1 2 1 1 0 0 0 0 0 0 - 0 0 1 1 1 0 5 5 5 0 0 0 - 0 0 0 1 0 0 0 0 0 0 0 0 - 0 0 0 0 0 5 0 0 1 0 0 0 - 0 0 0 0 5 0 0 1 2 1 0 0 - 0 0 0 5 0 0 1 2 15 2 1 0 - 0 0 5 0 0 0 0 1 2 1 0 0 - 0 0 0 0 0 0 0 0 1 0 0 0 diff --git a/02. Podslika/XDS/MALA.SLI b/02. Podslika/XDS/MALA.SLI deleted file mode 100644 index a05cae8..0000000 --- a/02. Podslika/XDS/MALA.SLI +++ /dev/null @@ -1,6 +0,0 @@ -5 - 0 0 1 0 0 - 0 1 1 1 0 - 1 1 2 1 1 - 0 1 1 1 0 - 0 0 1 0 0 diff --git a/02. Podslika/XDS/PODSLIKA.MOD b/02. Podslika/XDS/PODSLIKA.MOD deleted file mode 100644 index 5310154..0000000 --- a/02. Podslika/XDS/PODSLIKA.MOD +++ /dev/null @@ -1,168 +0,0 @@ -MODULE Podslika; - - FROM FIO IMPORT - File, Open, Close, RdCard, EOF, 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 - - Slika = ARRAY [1 .. MaxDim], [1 .. MaxDim] OF CARDINAL; - - VAR - Velika, Mala: Slika; - DimVel, DimMal, Vr, Ko: CARDINAL; - KljucMale, KljucSegmenta, Stepen: CARDINAL; - 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): CARDINAL; - VAR - i, j: CARDINAL; - Kljuc, ZbirKolone, Temp: CARDINAL; - 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 + (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: CARDINAL); - VAR - j: CARDINAL; - ZbirKolone, Temp: CARDINAL; - BEGIN - - ZbirKolone:= 0; - FOR j:= Vr TO Vr + DimMal - 1 DO - ZbirKolone:= ZbirKolone + (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 + (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. diff --git a/02. Podslika/XDS/VELIKA.SLI b/02. Podslika/XDS/VELIKA.SLI deleted file mode 100644 index 050166c..0000000 --- a/02. Podslika/XDS/VELIKA.SLI +++ /dev/null @@ -1,13 +0,0 @@ -12 - 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 1 0 0 0 0 0 0 0 0 - 0 0 1 1 1 0 0 0 0 0 0 0 - 0 1 1 2 1 1 0 0 0 0 0 0 - 0 0 1 1 1 0 5 5 5 0 0 0 - 0 0 0 1 0 0 0 0 0 0 0 0 - 0 0 0 0 0 5 0 0 1 0 0 0 - 0 0 0 0 5 0 0 1 2 1 0 0 - 0 0 0 5 0 0 1 2 15 2 1 0 - 0 0 5 0 0 0 0 1 2 1 0 0 - 0 0 0 0 0 0 0 0 1 0 0 0 diff --git a/02. Trazenje podslike/Prezentacija.ppt b/02. Trazenje podslike/Prezentacija.ppt new file mode 100644 index 0000000..0c685f2 Binary files /dev/null and b/02. Trazenje podslike/Prezentacija.ppt differ diff --git a/02. Trazenje podslike/TopSpeed/MALA.SLI b/02. Trazenje podslike/TopSpeed/MALA.SLI new file mode 100644 index 0000000..a05cae8 --- /dev/null +++ b/02. Trazenje podslike/TopSpeed/MALA.SLI @@ -0,0 +1,6 @@ +5 + 0 0 1 0 0 + 0 1 1 1 0 + 1 1 2 1 1 + 0 1 1 1 0 + 0 0 1 0 0 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. diff --git a/02. Trazenje podslike/TopSpeed/VELIKA.SLI b/02. Trazenje podslike/TopSpeed/VELIKA.SLI new file mode 100644 index 0000000..050166c --- /dev/null +++ b/02. Trazenje podslike/TopSpeed/VELIKA.SLI @@ -0,0 +1,13 @@ +12 + 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 1 0 0 0 0 0 0 0 0 + 0 0 1 1 1 0 0 0 0 0 0 0 + 0 1 1 2 1 1 0 0 0 0 0 0 + 0 0 1 1 1 0 5 5 5 0 0 0 + 0 0 0 1 0 0 0 0 0 0 0 0 + 0 0 0 0 0 5 0 0 1 0 0 0 + 0 0 0 0 5 0 0 1 2 1 0 0 + 0 0 0 5 0 0 1 2 15 2 1 0 + 0 0 5 0 0 0 0 1 2 1 0 0 + 0 0 0 0 0 0 0 0 1 0 0 0 diff --git a/02. Trazenje podslike/XDS/MALA.SLI b/02. Trazenje podslike/XDS/MALA.SLI new file mode 100644 index 0000000..a05cae8 --- /dev/null +++ b/02. Trazenje podslike/XDS/MALA.SLI @@ -0,0 +1,6 @@ +5 + 0 0 1 0 0 + 0 1 1 1 0 + 1 1 2 1 1 + 0 1 1 1 0 + 0 0 1 0 0 diff --git a/02. Trazenje podslike/XDS/PODSLIKA.MOD b/02. Trazenje podslike/XDS/PODSLIKA.MOD new file mode 100644 index 0000000..5310154 --- /dev/null +++ b/02. Trazenje podslike/XDS/PODSLIKA.MOD @@ -0,0 +1,168 @@ +MODULE Podslika; + + FROM FIO IMPORT + File, Open, Close, RdCard, EOF, 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 + + Slika = ARRAY [1 .. MaxDim], [1 .. MaxDim] OF CARDINAL; + + VAR + Velika, Mala: Slika; + DimVel, DimMal, Vr, Ko: CARDINAL; + KljucMale, KljucSegmenta, Stepen: CARDINAL; + 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): CARDINAL; + VAR + i, j: CARDINAL; + Kljuc, ZbirKolone, Temp: CARDINAL; + 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 + (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: CARDINAL); + VAR + j: CARDINAL; + ZbirKolone, Temp: CARDINAL; + BEGIN + + ZbirKolone:= 0; + FOR j:= Vr TO Vr + DimMal - 1 DO + ZbirKolone:= ZbirKolone + (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 + (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. diff --git a/02. Trazenje podslike/XDS/VELIKA.SLI b/02. Trazenje podslike/XDS/VELIKA.SLI new file mode 100644 index 0000000..050166c --- /dev/null +++ b/02. Trazenje podslike/XDS/VELIKA.SLI @@ -0,0 +1,13 @@ +12 + 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 0 0 0 0 0 + 0 0 0 1 0 0 0 0 0 0 0 0 + 0 0 1 1 1 0 0 0 0 0 0 0 + 0 1 1 2 1 1 0 0 0 0 0 0 + 0 0 1 1 1 0 5 5 5 0 0 0 + 0 0 0 1 0 0 0 0 0 0 0 0 + 0 0 0 0 0 5 0 0 1 0 0 0 + 0 0 0 0 5 0 0 1 2 1 0 0 + 0 0 0 5 0 0 1 2 15 2 1 0 + 0 0 5 0 0 0 0 1 2 1 0 0 + 0 0 0 0 0 0 0 0 1 0 0 0