Pagini recente » Cod sursa (job #1425085) | Cod sursa (job #2173963) | Cod sursa (job #2217872) | Cod sursa (job #1314969) | Cod sursa (job #205480)
Cod sursa(job #205480)
# include <stdio.h>
# include <string.h>
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
int N=1,len,i,state,j,ok,Sol,k,l;
int Q[Nod][Sigma];
int U[Nod][Sigma];
int stack[Nod];
int Fail[Nod];
uc Ac[Nod];
char D[DMAX];
char s[LMAX];
void trie(char *s)
{
state = 1;
for (char *c = s; *c ; ++c)
{
i = *c - 'a';
if (Q[state][i])
state = Q[state][i];
else
{
Q[state][i] = ++N;
state = N;
}
}
Ac[N] = 1;
}
void compute(char *s)
{
state = 1;
for (char *c = s; *c ; ++c)
{
i = *c - 'a';
state = U[state][i];
Sol += Ac[state];
}
}
void failure()
{
int sf = 0,u,i;
for (i = 0; i < 3; ++i)
{
U[1][i] = 1;
if (Q[1][i] != 1)
{
stack[sf++]=Q[1][i];
Fail[Q[1][i]] = 1;
U[1][i] = Q[1][i];
}
}
for (i = 0; i < sf; ++i)
{
for (j = 0; j < 3; ++j)
if (Q[stack[i]][j])
{
stack[sf++] = Q[stack[i]][j];
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;
}
for (l = 0; l < Sigma; ++l)
{
if (Q[stack[i]][l] != 0)
U[stack[i]][l]=Q[stack[i]][l];
else
U[stack[i]][l]=U[Fail[stack[i]]][l];
if (U[stack[i]][l] == 0)
U[stack[i]][l] = 1;
}
}
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf(" %s ",D);
for (l = 0; scanf(" %s ",s) != EOF; )
trie(s);
for (i = 0; i < 3; ++i)
if (Q[1][i] == 0) Q[1][i] = 1;
failure();
compute(D);
printf("%d",Sol);
return 0;
}