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
30
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main (int argc, char ** argv) { /* vzorec je prvi argument, slovar je standardni vhod */
if (argc != 2) {
fprintf(stderr, "uporaba: %s vzorec < slovar.txt\n", argv[0] ? argv[0] : "pwnkit");
return 1; /* slovar so besede v cevovodu, ločene z novo vrstico tipa POSIX */
}
int l = strlen(argv[1]); /* dolžina vzorca, daljše besede avtomatsko izključimo */
char * buf = alloca(l+2); /* prostor za vrstico vnosa slovarja */
#define NASLEDNJI() while (!fgets(buf, l+2, stdin) && !feof(stdin)) /* predolgi grejo takoj stran */
NASLEDNJI();
while (!feof(stdin)) { /* beremo vsako besedo slovarja */
for (int i = 0; 1; i++) { /* gremo čez vsak znak besede iz slovarja in znak vzorca */
if (buf[i] == '\n' && !argv[1][i]) { /* če je hkrati konec besede & vzorca */
printf("%s", buf); /* itak je nova vrstica že v buf */
break; /* natisnemo besedo in gremo na naslednjo besedo */
}
if (buf[i] == '\n' || (buf[i] != argv[1][i] && argv[1][i] != '*'))
break; /* če je konec besede in ni konec vzorca ali obratno */
} /* potem ne izpišemo */
NASLEDNJI();
}
return 0; /* končamo program */
}
/*
podprimer b:
Vse besede bi shranili v delovni pomnilnik v drevesno strukturo s primerjalno funkcijo strcmp, vendar bi imeli za vsako dolžino besede svojo drevesno strukturo. Z drevesno strukturo smo olajšali kompleksnost iskanja besed, kjer je pri vzorcu na začetku veliko določenih znakov in ne zvezdic. Ko pri vzorcu pridemo do prve zvezdice, bo itak treba iskati po vsej veji v drevesu. Dodajanje dreves še od zadaj naprej bi samo povečalo spominsko zahtevnost. S ločevanjem po dolžini nizov pa smo zmanjšali kompleksnost, ko vzorec blizu začetka če vsebuje zvezdico a ni iste dolžine (takoj bo zavrnjen, če te dolžine v slovarju ni in zmanjša iskalno polje), nismo pa bistveno vplivali na spominsko zahtevnost.
*/
|
