Pagini recente » Cod sursa (job #2912298) | Cod sursa (job #2616106) | Cod sursa (job #1946176) | Cod sursa (job #2856444) | Cod sursa (job #104544)
Cod sursa(job #104544)
#include <stdio.h>
#include <string.h>
#define MaxNodes 1000005
#define NMax 10000005
char S[NMax], cuv[25], F[MaxNodes];
int trie[MaxNodes][3], A[MaxNodes][3], up[MaxNodes], nodes = 1;
int q[MaxNodes], cnt;
void build_automaton(void)
{
int c, ql = 0, qr, x, t;
for (q[0] = 1, c = 0; c < 3; c++)
{
A[1][c] = 1;
if (trie[1][c])
q[++ql] = trie[1][c],
up[q[ql]] = 1;
}
for (qr = 1; qr <= ql; qr++)
{
x = q[qr];
for (c = 0; c < 3; c++)
if (trie[up[x]][c] == x)
break;
t = A[up[x]][c];
A[up[x]][c] = x;
for (c = 0; c < 3; c++)
{
if (trie[t][c])
A[x][c] = trie[t][c];
else
A[x][c] = A[t][c];
if (trie[x][c])
q[++ql] = trie[x][c],
up[q[ql]] = x;
}
}
}
int main(void)
{
int i, nod, L = -1, len;
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
fgets(S, sizeof(S), stdin);
while (fgets(cuv, sizeof(cuv), stdin) != NULL)
{
if (L == -1)
for (L = 0; cuv[L] >= 'a' && cuv[L] <= 'c'; L++);
for (i = 0, nod = 1; i < L; i++)
{
if (cuv[i] < 'a' || cuv[i] >'c') break;
if (!trie[nod][cuv[i]-'a'])
trie[nod][cuv[i]-'a'] = (++nodes);
nod = trie[nod][cuv[i]-'a'];
}
F[nod] = 1;
}
build_automaton();
for (i = 0, nod = 1, len = strlen(S); i < len; ++i)
{
if (S[i] < 'a' || S[i] > 'c') break;
nod = A[nod][S[i]-'a'];
cnt += (F[nod] == 1);
}
printf("%d\n", cnt);
return 0;
}