path: root/inf/rtk/2020-offline/npk.c

#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