Pagini recente » Cod sursa (job #1465263) | Cod sursa (job #2813197) | Cod sursa (job #2917177) | Monitorul de evaluare | Cod sursa (job #205372)
Cod sursa(job #205372)
# include <stdio.h>
# include <string.h>
# include <vector>
using namespace std;
# define FIN "abc2.in"
# define FOUT "abc2.out"
# define DMAX 10000010
# define LMAX 21
# define Nod 1000010
# define Sigma 3
# define uc unsigned char
uc Ac[Nod];
int Q[Nod][Sigma];
int Fail[Nod];
int N = 1,len,i,state,j,ok=0,Sol=0,k=0;
char D[DMAX];
char s[LMAX];
vector <int> stack;
void trie(char *s)
{
/*if (ok == 0)
{
len = strlen(s);
ok = 1;
}*/
state = 1;
for (char *c = s; *c ; ++c)
{
i = *c - 'a';
if (Q[state][i] != 0)
state = Q[state][i];
else
{
Q[state][i] = ++N;
state = N;
}
}
Ac[N] = 1;
}
void failure()
{
int sf = 0,u,i;
for (i = 0; i < 3; ++i)
if (Q[1][i] != 1)
{
stack.push_back(Q[1][i]);
sf++;
Fail[Q[1][i]] = 1;
}
for (i = 0; i < sf; ++i)
for (j = 0; j < 3; ++j)
if (Q[stack[i]][j] != 0)
{
stack.push_back(Q[stack[i]][j]);
sf++;
u = Fail[stack[i]];
while (Q[u][j] == 0)
u = Fail[u];
Fail[Q[stack[i]][j]] = Q[u][j];
if (Ac[Fail[Q[stack[i]][j]]] == 1)
Ac[Q[stack[i]][j]] = 1;
}
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
gets(D);
while (!feof(stdin))
{
gets(s);
trie(s);
}
for (i = 0; i < 3; ++i)
if (Q[1][i] == 0) Q[1][i] = 1;
failure();
len = strlen(D);
state = 1;
for (i = 0; i < len; ++i)
{
while (Q[state][D[i]-'a'] == 0)
state = Fail[state];
state = Q[state][D[i]-'a'];
Sol += Ac[state];
}
printf("%d",Sol);
return 0;
}