summaryrefslogtreecommitdiffstats
path: root/inf/rtk/2020-offline/resi.c
diff options
context:
space:
mode:
authorsijanec <anton@sijanec.eu>2021-01-15 08:22:07 +0100
committersijanec <anton@sijanec.eu>2021-01-15 08:22:07 +0100
commit2057a987a330e086659a9bf95fa69cf168f861a3 (patch)
treec316b35c9562ec2c8a513ae9cb364d5a32833663 /inf/rtk/2020-offline/resi.c
parent22. domača naloga za matematiko (diff)
downloadsola-gimb-2-2057a987a330e086659a9bf95fa69cf168f861a3.tar
sola-gimb-2-2057a987a330e086659a9bf95fa69cf168f861a3.tar.gz
sola-gimb-2-2057a987a330e086659a9bf95fa69cf168f861a3.tar.bz2
sola-gimb-2-2057a987a330e086659a9bf95fa69cf168f861a3.tar.lz
sola-gimb-2-2057a987a330e086659a9bf95fa69cf168f861a3.tar.xz
sola-gimb-2-2057a987a330e086659a9bf95fa69cf168f861a3.tar.zst
sola-gimb-2-2057a987a330e086659a9bf95fa69cf168f861a3.zip
Diffstat (limited to 'inf/rtk/2020-offline/resi.c')
-rw-r--r--inf/rtk/2020-offline/resi.c67
1 files changed, 67 insertions, 0 deletions
diff --git a/inf/rtk/2020-offline/resi.c b/inf/rtk/2020-offline/resi.c
new file mode 100644
index 0000000..43f97cc
--- /dev/null
+++ b/inf/rtk/2020-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