From 2057a987a330e086659a9bf95fa69cf168f861a3 Mon Sep 17 00:00:00 2001
From: sijanec <anton@sijanec.eu>
Date: Fri, 15 Jan 2021 08:22:07 +0100
Subject: =?UTF-8?q?joj=20=C5=A1ol?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 inf/rtk/2020-offline/npk.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)
 create mode 100644 inf/rtk/2020-offline/npk.c

(limited to 'inf/rtk/2020-offline/npk.c')

diff --git a/inf/rtk/2020-offline/npk.c b/inf/rtk/2020-offline/npk.c
new file mode 100644
index 0000000..a18b38a
--- /dev/null
+++ b/inf/rtk/2020-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
-- 
cgit v1.2.3