Pagini recente » Cod sursa (job #649329) | Cod sursa (job #2073385) | Cod sursa (job #1494447) | Monitorul de evaluare | Cod sursa (job #614922)
Cod sursa(job #614922)
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAXN 10000010
struct nod {
nod *fii[4];
};
long i, len, QUE, sol, j;
char s[MAXN], sir[25];
nod *p, *trie, *trie2, *que[1000010], *back, *aux;
int main() {
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
scanf("%s", s);
p = new nod;
for (i = 0; i < 4; ++i) p->fii[i] = NULL;
while (scanf("%s", sir) == 1) {
fprintf(stderr, "%s\n", sir);
len = strlen(sir);
trie = p;
for (i = 0; i < len; ++i) {
if (trie->fii[sir[i] - 'a'] == NULL) {
fprintf(stderr, "Aloc %d\n", i);
trie->fii[sir[i] - 'a'] = new nod;
for (j = 0; j < 4; ++j) trie->fii[sir[i] - 'a']->fii[j] = NULL;
trie = trie->fii[sir[i] - 'a'];
} else {
trie = trie->fii[sir[i] - 'a'];
}
}
}
for (i = 0; i < 3; ++i) {
if (p->fii[i] != NULL) {
p->fii[i]->fii[3] = p;
que[++QUE] = p->fii[i];
}
}
for (i = 1; i <= QUE; ++i) {
trie2 = que[i];
back = trie2->fii[3];
aux = back;
for (j = 0; j < 3; ++j) {
back = aux;
if (trie2->fii[j] != NULL) {
while (back->fii[j] == NULL && back != p) {
back = back->fii[3];
}
if (back->fii[j] != NULL) {
trie2->fii[j]->fii[3] = back->fii[j];
} else {
trie2->fii[j]->fii[3] = back;
}
que[++QUE] = trie2->fii[j];
}
}
}
len = strlen(s);
for (i = 0; i < len; ++i) {
while (p->fii[s[i] - 'a'] == NULL && p->fii[3] != NULL) {
p = p->fii[3];
}
if (p->fii[s[i] - 'a'] != NULL) {
p = p->fii[s[i] - 'a'];
}
long ok = 0;
for (j = 0; j < 3; ++j) {
if (p->fii[j] != NULL) {
ok = 1;
break;
}
}
if (ok == 0) {
++sol;
}
}
printf("%ld\n", sol);
return 0;
}