blob: cbe4ba42f40cfe580739a47d775f7a23df22ddbb (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}
|
