summaryrefslogtreecommitdiffstats
path: root/inf/rtk
diff options
context:
space:
mode:
Diffstat (limited to 'inf/rtk')
-rw-r--r--inf/rtk/offline/.gitignore4
-rw-r--r--inf/rtk/offline/Makefile23
-rw-r--r--inf/rtk/offline/npk.c60
-rw-r--r--inf/rtk/offline/offline.h8
-rw-r--r--inf/rtk/offline/origprog.c78
-rw-r--r--inf/rtk/offline/razdeli.c65
-rw-r--r--inf/rtk/offline/resi.c67
-rw-r--r--inf/rtk/offline/test.txt2
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 @@
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-24 18:01:51 +0100