Pagini recente » Cod sursa (job #2902590) | Cod sursa (job #148436) | Cod sursa (job #972492) | Cod sursa (job #1791174) | Cod sursa (job #99124)
Cod sursa(job #99124)
#include <stdio.h>
#include <string.h>
#define MaxNodes 1000005
#define NMax 10000005
char S[NMax], cuv[32];
int trie[MaxNodes][3], pi[MaxNodes], A[MaxNodes][3], dep[MaxNodes], nodes;
int q[MaxNodes], cnt;
void build_automaton(void)
{
int i, c, p, ql, qr;
for (q[ql=qr=0]=0, pi[0] = -1; qr <= ql; qr++)
for (c = 0; c < 3; c++)
if (trie[q[qr]][c] != -1)
{
q[++ql] = trie[q[qr]][c];
for (p = pi[q[qr]]; p >= 0 && trie[p][c] == -1; p = pi[p]);
if (p == -1) pi[q[ql]] = 0;
else pi[q[ql]] = trie[p][c];
}
for (i = 0; i <= nodes; i++)
for (c = 0; c < 3; c++)
if (trie[i][c] != -1)
A[i][c] = trie[i][c];
else
{
for (p = pi[i]; p >= 0 && trie[p][c] == -1; p = pi[p]);
if (p == -1) A[i][c] = 0;
else A[i][c] = trie[p][c];
}
}
int main(void)
{
int i, nod, L = -1, len;
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
memset(trie, -1, sizeof(trie));
fgets(S, sizeof(S), stdin);
while (scanf("%s", &cuv) != EOF)
{
if (L == -1) L = strlen(cuv);
for (i = nod = 0; i < L; i++)
if (trie[nod][cuv[i]-'a'] == -1)
++nodes,
dep[nodes] = dep[nod] + 1,
trie[nod][cuv[i]-'a'] = nodes,
nod = nodes;
else
nod = trie[nod][cuv[i]-'a'];
}
build_automaton();
for (i = nod = 0, len = strlen(S); i < len; i++)
{
if (S[i] < 'a' || S[i] > 'c') break;
nod = A[nod][S[i]-'a'];
cnt += (dep[nod] == L);
}
printf("%d\n", cnt);
return 0;
}