Pagini recente » Cod sursa (job #1157968) | Cod sursa (job #1186680) | Cod sursa (job #2569591) | Cod sursa (job #278720) | Cod sursa (job #205362)
Cod sursa(job #205362)
# include <stdio.h>
# include <string.h>
# include <vector>
using namespace std;
# define FIN "abc2.in"
# define FOUT "abc2.out"
# define DMAX 10000001
# define LMAX 21
# define Nod 1000001
# 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;
char D[DMAX];
char s[LMAX];
vector <int> stack;
void trie()
{
if (ok == 0)
{
len = strlen(s)-1;
ok = 1;
}
state = 1;
for (i = 0; i < len; ++i)
{
if (Q[state][s[i]-'a'] != 0)
state = Q[state][s[i]-'a'];
else
{
Q[state][s[i]-'a'] = ++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);
fgets(D,DMAX,stdin);
while (!feof(stdin))
{
fgets(s,LMAX,stdin);
trie();
}
for (i = 0; i < 3; ++i)
if (Q[1][i] == 0) Q[1][i] = 1;
failure();
int Sol = 0;
len = strlen(D)-1;
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;
}