diff options
Diffstat (limited to '')
-rw-r--r-- | inf/rtk/2021-državno/4/prog.c | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/inf/rtk/2021-državno/4/prog.c b/inf/rtk/2021-državno/4/prog.c new file mode 100644 index 0000000..cbe4ba4 --- /dev/null +++ b/inf/rtk/2021-državno/4/prog.c @@ -0,0 +1,29 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +int Primerjava (char * s, char * t, int n) { /* O(2n) */ + int d = strlen(s); /* predpomnimo dolžino testov */ + int sest = 0; /* sestevek naj bo 0 */ + for (int i = 0; i < n; i++) /* najprej je iskalniško okno prvih n, zato naredimo seštevek */ + if (s[i] != t[i]) /* če je diskrepanca */ + sest++; /* povečamo seštevek */ + int topsest = sest; /* največji seštevek je torej seštevek */ + int topoffs = 0; /* zapomnimo si offset tega največjega seštevka */ + for (int i = n; i < d; i++) { /* hodimo po nizu in premikamo okno */ + if (s[i-n] != t[i-n]) /* če se na začetku pregledovalnega okna testa nista ujemala */ + sest--; /* zmanjšamo seštevek, ker tega ni več v oknu */ + if (s[i] != t[i]) /* če se nova v okno ne skladata */ + sest++; /* povečamo seštevek neujemanih */ + if (sest > topsest) /* če je v oknu nov rekordni seštevek */ + topoffs = (i-n)+1; /* offset spremenimo na trenutni offset začetka okna - pazi, to ni i-n, kajti tega smo iz okna pravkar izpustili */ + } + return topoffs; /* vrnemo offset največjega seštevka */ +} +int main (int argc, char ** argv) { + if (argc < 1+3) { + fprintf(stderr, "uporaba: %s <niz s> <niz t> <celo n>\n", argv[0]); + return 1; + } + fprintf(stdout, "rekordni offset je %d\n", Primerjava(argv[1], argv[2], atoi(argv[3]))); /* iz glavne funkcije poženemo podpr. */ + return 0; +} |