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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct niz {
int d; /* dolzina niza */
char * n; /* niz */
};
/* funkcija odvrne 0, ce sta niza enako dolga, -1, ce je prvi krajsi od drugega in 1, ce je prvi daljsi od drugega */
int primerjaj_niza (const void * a, const void * b) {
const struct niz * sna = (const struct niz *) a; /* Cjeva carovnija vlivanja */
const struct niz * snb = (const struct niz *) b;
return (sna->d > snb->d) - (sna->d < snb->d); /* preprosto primerjanje dveh stevilk */
}
struct niz * podprogram (
struct niz * n, /* seznam nizov */
int nizov, /* stevilo nizov */
struct niz * p /* prejsnji niz za rekurzijo */
) {
int i = 0; /* iteracijski decek */
int j = 0; /* iteracijski decek, ki je potopljen v 1. globino vgnezdene zanke */
int o = 0; /* oddaljenost prvega niza, ki ima vecjo dolzino */
int s = 0; /* ali smo ze en znak izpustili */
int a = 1; /* niz je aplikatibilen */
struct niz * od = p; /* kazalec na odgovor, nastavljen na prejsnji niz, ce nizi te velikosti niso vec aplikatibilni */
struct niz * op; /* kazalec na prihodnji morebitni odgovor, seveda zgolj, ce je daljsi */
int zadnja_runda = 0; /* samoumevno */
for (o = 0; n[o].d == n[0].d; o++) /* za vsak niz najkrajse dolzine */
if (o+1 >= nizov) { /* ce smo pri koncu seznama nizov */
zadnja_runda = 1; /* pri koncu seznama nizov smo, to si zabelezimo */
o++; /* ker se pri break tretji stavek for zanke ne izvede na koncu */
break;
}
for (i = 0; i < o; i++) { /* podobno kot prejsnja zanka, le da jnam je sedaj o znan */
s = 0; /* ponastavimo */
a = 1; /* ponastavimo */
for (j = 0; j < p->d; j++) { /* za vsak znak prejsnjega niza */
if (p->n[j] != n[i].n[j+s]) /* ce se nas niz za en znak vec ne ujema s prejsnjim */
s++;
if (s > 1) { /* ce se je prejsen ce stavek ze zgodil, smo izpustili ze dva znaka, kar ni dovoljeno */
a = 0; /* ta niz ni aplikatibilen */
break;
}
}
if (a && zadnja_runda) /* ce smo pri koncu in smo nasli aplikatibien niz - super, vrnemo ga skozi rekurzicno verigo, to je niz, ki ga iscemo (;:! */
return &n[i]; /* ja, spet bi lahko uporabil n+i ampak se mi tole zdi lepše */
if (a) {
op = podprogram(n+o, nizov-o, &n[i]); /* poklicemo podprogram z mnozico nizov zgolj vecjih velikosti, kot ta velikost - zato potrebujemo o (: */
if (op != NULL && op->d > od->d) /* ce je odgovor boljsi od do sedaj znanega */
od = op; /* kazalec na starega prepisemo */
}
}
return od;
}
/* argv+1 je seznam nizov.
* */
#if __INCLUDE_LEVEL__ == 0
int main (int argc, char ** argv) {
if (argc < 1+1) {
fprintf(stderr, "uporaba: %s splatters splatter platter latter later late ate at a (nenujno po velikosti)\n", argv[0]);
return 1;
}
struct niz * n = malloc(sizeof(struct niz)*argc); /* prostor za nize */
size_t i = 0; /* iteracijski decek */
struct niz * o; /* odgovor */
struct niz p = { /* virtualen prejsnji niz, ki ga damo v rekurzicno funkcijo */
.d = 0,
.n = "",
}; /* zato, da ni treba delati dodatnega preizkusa, ce je funkcija podprogram pognana iz funkcije podprogram ali iz uporabnkove funkcije, recimo main */
for (i = 0; i < argc-1; i++) { /* pridobimo velikosti nizov */
n[i].d = strlen(argv[1+i]); /* predpomnimo dolzino niza */
n[i].n = argv[i+1]; /* zapisemo kazalec do konstantnega niza iz argv */
}
/* sedaj pa nize razvrstimo po velikosti s funkcijo iz STANDARDNE KNJIZNICE qsort */
qsort(n, argc-1, sizeof(struct niz), primerjaj_niza);
/* sedaj pa lahko zacnemo z nasim skriptom */
o = podprogram(n, argc-1, &p);
fprintf(stdout, "%s\n", o->n);
free(n);
n = NULL;
return 0;
}
#endif
|
