summaryrefslogtreecommitdiffstats
path: root/inf/rtk/offline/npk.c
diff options
context:
space:
mode:
Diffstat (limited to 'inf/rtk/offline/npk.c')
-rw-r--r--inf/rtk/offline/npk.c60
1 files changed, 60 insertions, 0 deletions
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