8 files changed, 307 insertions, 0 deletions

diff --git a/inf/rtk/offline/.gitignore b/inf/rtk/offline/.gitignore
new file mode 100644
index 0000000..ffeb5c9
--- /dev/null
+++ b/inf/rtk/offline/.gitignore
@@ -0,0 +1,4 @@
+stiskanje-unix.in
+stiskanje.in
+naloge/
+*.out
diff --git a/inf/rtk/offline/Makefile b/inf/rtk/offline/Makefile
new file mode 100644
index 0000000..dde543e
--- /dev/null
+++ b/inf/rtk/offline/Makefile
@@ -0,0 +1,23 @@
+default:
+	@echo "offline naloga in rešitev za ijs.rtk. recepti:"
+	@echo "- make prepare: prenese datoteke, potrebne za nalogo"
+	@echo "- make razdeli: razdeli naloge v posamezne datoteke"
+	@echo "- make npk: naredi program za najdaljši ponavljajoči kos"
+	@echo "- make resi: naredi program za reševanje"
+
+prepare:
+	wget http://rtk.ijs.si/2020/stiskanje/stiskanje-unix.in -c
+	wget http://rtk.ijs.si/2020/stiskanje/stiskanje.in -c
+
+resi:
+	gcc -Wall -pedantic -I. -g -oresi.out resi.c
+
+npk:
+	gcc -Wall -pedantic -I. -g -onpk.out npk.c
+
+razdeli:
+	gcc -Wall -pedantic -I. -g -orazdeli.out razdeli.c
+	./razdeli.out < stiskanje-unix.in
+	rm -rf naloge
+	mkdir -p naloge
+	mv naloga*.txt naloge/
diff --git a/inf/rtk/offline/npk.c b/inf/rtk/offline/npk.c
new file mode 100644
index 0000000..a18b38a
--- /dev/null
+++ b/inf/rtk/offline/npk.c
@@ -0,0 +1,60 @@
+#if __INCLUDE_LEVEL__ != 0
+#pragma once
+#endif
+/* najdaljši ponavljajoči kos niza */
+#include <stdio.h>
+#include <stdlib.h>
+#include <offline.h>
+#include <string.h>
+/* lahko bi šli čez niz znakov for(strlen)for(strlen)for(strlen), ampak to
+ * bi trajalo zelo dolgo, čas*1000000^3 in bi imelo O(n^3) kompleksnost.
+ * ta implementacija najde najdaljši string in ima kompleksnost
+ * PRIBLIŽNO OKOLI O(n^2), kar je bistveno hitreje, PRIBLIŽNO čas*1000000^2. */
+struct rtk_kos npk (char * s) {
+	struct rtk_kos k;
+	k.l = 0; k.o = 0; 
+	const size_t l = strlen(s);
+	unsigned char ** z = calloc(l+1, sizeof(unsigned char *));
+	size_t i = 0;
+	size_t j = 0;
+	for (i = 0; i < l+1; i++)
+		z[i] = calloc(l+1, sizeof(unsigned char));
+	for (i = 1; i <= l; i++)
+		for (j = i+1; j <= l; j++)
+			if (s[i-1] == s[j-1] && z[i-1][j-1] < (j-1)) {
+				z[i][j] = z[i-1][j-1] + 1;
+				if (z[i][j] > k.l) {
+					k.l = z[i][j];
+					k.o = k.o > i ? k.o : i;
+				}
+			} else
+				z[i-1][j-1] = 0;
+	k.o = k.o-k.l;
+	for (i = 0; i < l+1; i++) {
+		free(z[i]); z[i] = NULL;
+	}
+	free(z);
+	z = NULL;
+	return k;
+}
+#if __INCLUDE_LEVEL__ == 0
+int main (int argc, char ** argv) {
+	char c = getchar();
+	size_t v = 0;
+	char * s = malloc(sizeof(char)*1);
+	struct rtk_kos k;
+	while (!feof(stdin)) {
+		s = realloc(s, sizeof(char)*v+2);
+		s[v++] = c;
+		s[v] = '\0';
+		c = getchar();
+	}
+	k = npk(s);
+	for (v = 0; v < k.l; v++)
+		putchar(s[v+k.o]);
+	putchar('\n'); /* za dobro mero */
+	free(s);
+	s = NULL;
+	return 0;
+}
+#endif
diff --git a/inf/rtk/offline/offline.h b/inf/rtk/offline/offline.h
new file mode 100644
index 0000000..9724846
--- /dev/null
+++ b/inf/rtk/offline/offline.h
@@ -0,0 +1,8 @@
+#define RTK_EOL '\r'
+#define RTK_IDC(x,y) (x/y + (x % y != 0)) /* int devide ceil */
+#define RTK_RAM_KOS 128
+struct rtk_kos {
+	size_t o; /* ffset */
+	size_t l; /* ength */
+	size_t p; /* ojavi */
+};
diff --git a/inf/rtk/offline/origprog.c b/inf/rtk/offline/origprog.c
new file mode 100644
index 0000000..631d61d
--- /dev/null
+++ b/inf/rtk/offline/origprog.c
@@ -0,0 +1,78 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <offline.h>
+size_t rtk_resi (/* const */ char * s, struct rtk_kos * p) {
+	size_t i = 0;
+	size_t j = 0;
+	size_t k = 0;
+	size_t l = strlen(s);
+	size_t p_sizeof = RTK_RAM_KOS; size_t pzi = 0; /* pieces za izdelavo */
+	size_t pjev = 0; size_t psd = 0; /* pieces sigma dolžin */;
+	/* struct rtk_kos * */ p = malloc(sizeof(struct rtk_kos)*p_sizeof);
+	/* začnemo s preprosto rešitvijo: en kos, celoten niz */
+	p[0].o = 0; p[0].l = l; p[0].p = 1; pjev++; psd = l; pzi = 1;
+	/* iščemo ponovitve za izboljšavo, začnemo z dolžino 2 */
+	/* kosov, velikih 1, še ne potrebujemo */
+	/* POMNI: izračun točk: psd+pzi */
+	for (i = 2; i < l; i++) { /* za vsako možno dolžino kosa */
+		for (j = 0; j < l-i; j++) { /* za vsako lokacijo, kjer bi se začel kos */
+			// fprintf(stderr, "%.*s\n", i, s+j);
+		}
+	}
+	return pjev;
+}
+int main (int argc, char ** argv) {
+	char ** n = malloc(sizeof(char *) * 1);
+	size_t * v = malloc(sizeof(size_t) * 1);
+	size_t nalog = 0;
+	int returnstatus = 0;
+	char c = getchar();
+	int vrs = 0;
+	size_t pjev;
+	char fn[69];
+	FILE * fd;
+	struct rtk_kos * p;
+	n[0] = NULL;
+	v[0] = 0;
+	while (!feof(stdin)) {
+		n[nalog] = realloc(n[nalog], sizeof(char)*v[nalog]+2);
+		n[nalog][v[nalog]++] = c;
+		n[nalog][v[nalog]] = '\0';
+		if (c == RTK_EOL) {
+			if (vrs == 0 && strncmp("Stiskanje", n[0], strlen("Stiskanje") != 0)) {
+				fprintf(stderr, "vhodna datoteka se ne začne s \"Stiskanje\"\n");
+				returnstatus = 1;
+				goto returncleanly;
+			}
+			if ((vrs - 2) % 3 == 2) { /* če je bila to naloga */
+				fprintf(stderr, "prepisal nalogo %lu\r", nalog);
+				nalog++;
+				n = realloc(n, sizeof(char*)*(nalog+1));
+				n[nalog] = NULL;
+				v = realloc(v, sizeof(size_t)*(nalog+1));
+			}
+			v[nalog] = 0; /* gremo na začetek prostora za nalogo */
+			vrs++;
+		}
+		c = getchar();
+	}
+	fprintf(stderr, "zapisal naloge v spomin.         \n");
+	for (vrs = 0; vrs < nalog; vrs++) {
+		fprintf(stderr, "rešujem nalogo %d\n", vrs);
+		pjev = rtk_resi(n[vrs], p);
+		free(p);
+		p = NULL;
+	}
+	returncleanly:
+	while (nalog > 0) {
+		nalog--;
+		free(n[nalog]);
+		n[nalog] = NULL;
+	}
+	free(n);
+	n = NULL;
+	free(v);
+	v = NULL;
+	return returnstatus;
+}
diff --git a/inf/rtk/offline/razdeli.c b/inf/rtk/offline/razdeli.c
new file mode 100644
index 0000000..24c36c1
--- /dev/null
+++ b/inf/rtk/offline/razdeli.c
@@ -0,0 +1,65 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <offline.h>
+int main (int argc, char ** argv) {
+	char ** n = malloc(sizeof(char *) * 1);
+	size_t * v = malloc(sizeof(size_t) * 1);
+	size_t nalog = 0;
+	int returnstatus = 0;
+	char c = getchar();
+	int vrs = 0;
+	size_t pjev;
+	char fn[69];
+	FILE * fd;
+	/* struct rtk_kos * p; */
+	n[0] = NULL;
+	v[0] = 0;
+	while (!feof(stdin)) {
+		n[nalog] = realloc(n[nalog], sizeof(char)*v[nalog]+2);
+		n[nalog][v[nalog]++] = c;
+		n[nalog][v[nalog]] = '\0';
+		if (c == RTK_EOL) {
+			if (vrs == 0 && strncmp("Stiskanje", n[0], strlen("Stiskanje") != 0)) {
+				fprintf(stderr, "vhodna datoteka se ne začne s \"Stiskanje\"\n");
+				returnstatus = 1;
+				goto returncleanly;
+			}
+			if ((vrs - 2) % 3 == 2) { /* če je bila to naloga */
+				n[nalog][--v[nalog]] = '\0';
+				fprintf(stderr, "prepisal nalogo %lu\r", nalog);
+				nalog++;
+				n = realloc(n, sizeof(char*)*(nalog+1));
+				n[nalog] = NULL;
+				v = realloc(v, sizeof(size_t)*(nalog+1));
+			}
+			v[nalog] = 0; /* gremo na začetek prostora za nalogo */
+			vrs++;
+		}
+		c = getchar();
+	}
+	fprintf(stderr, "zapisal naloge v spomin.         \n");
+	for (vrs = 0; vrs < nalog; vrs++) {
+		fprintf(stderr, "shranjujem nalogo %d\n", vrs);
+		snprintf(fn, 69, "naloga%d.txt", vrs+1);
+		fd = fopen(fn, "w");
+		pjev = 0;
+		while (n[vrs][pjev] != '\0')
+			putc(n[vrs][pjev++], fd);
+		fprintf(stderr, "zadnji znak je %02x\n", n[vrs][--pjev]);
+		fclose(fd);
+		/* pjev = rtk_resi(n[vrs], p);
+		free(p); */
+	}
+	returncleanly:
+	while (nalog > 0) {
+		nalog--;
+		free(n[nalog]);
+		n[nalog] = NULL;
+	}
+	free(n);
+	n = NULL;
+	free(v);
+	v = NULL;
+	return returnstatus;
+}
diff --git a/inf/rtk/offline/resi.c b/inf/rtk/offline/resi.c
new file mode 100644
index 0000000..43f97cc
--- /dev/null
+++ b/inf/rtk/offline/resi.c
@@ -0,0 +1,67 @@
+#if __INCLUDE_LEVEL__ != 0
+#pragma once
+#endif
+/* najdaljši ponavljajoči kos niza */
+#include <stdio.h>
+#include <stdlib.h>
+#include <offline.h>
+#include <string.h>
+#define RTK_NAENKRAT 60000
+/* lahko bi šli čez niz znakov for(strlen)for(strlen)for(strlen), ampak to
+ * bi trajalo zelo dolgo, čas*1000000^3 in bi imelo O(n^3) kompleksnost.
+ * ta implementacija najde najdaljši string in ima kompleksnost
+ * PRIBLIŽNO OKOLI O(n^2), kar je bistveno hitreje, PRIBLIŽNO čas*1000000^2. */
+struct rtk_kos npk (const char * s, const size_t l) {
+	struct rtk_kos k;
+	k.l = 0; k.o = 0; 
+	unsigned char ** z = calloc(l+1, sizeof(unsigned char *));
+	size_t i = 0;
+	size_t j = 0;
+	for (i = 0; i < l+1; i++)
+		z[i] = calloc(l+1, sizeof(unsigned char));
+	for (i = 1; i <= l; i++)
+		for (j = i+1; j <= l; j++)
+			if (s[i-1] == s[j-1] && z[i-1][j-1] < (j-1)) {
+				z[i][j] = z[i-1][j-1] + 1;
+				if (z[i][j] > k.l) {
+					k.l = z[i][j];
+					k.o = k.o > i ? k.o : i;
+				}
+			} else
+				z[i-1][j-1] = 0;
+	k.o = k.o-k.l;
+	for (i = 0; i < l+1; i++) {
+		free(z[i]); z[i] = NULL;
+	}
+	free(z);
+	z = NULL;
+	return k;
+}
+#if __INCLUDE_LEVEL__ == 0
+int main (int argc, char ** argv) {
+	char c = getchar();
+	size_t v = 0;
+	char * s = malloc(sizeof(char)*1);
+	struct rtk_kos k1;
+	struct rtk_kos k2;
+	size_t l = 0;
+	while (!feof(stdin)) {
+		s = realloc(s, sizeof(char)*v+2);
+		s[v++] = c;
+		s[v] = '\0';
+		c = getchar();
+	}
+	l = v;
+	for (v = 0; v*RTK_NAENKRAT <= l;) {
+		k1 = npk(s+(v*(RTK_NAENKRAT/2)), RTK_NAENKRAT);
+		k2 = npk(s+(++v*(RTK_NAENKRAT/2)), RTK_NAENKRAT);
+	}
+	
+	for (v = 0; v < k.l; v++)
+		putchar(s[v+k.o]);
+	putchar('\n'); /* za dobro mero */
+	free(s);
+	s = NULL;
+	return 0;
+}
+#endif
diff --git a/inf/rtk/offline/test.txt b/inf/rtk/offline/test.txt
new file mode 100644
index 0000000..139597f
--- /dev/null
+++ b/inf/rtk/offline/test.txt
@@ -0,0 +1,2 @@
+
+