Pagini recente » Cod sursa (job #368581) | Cod sursa (job #685807) | Cod sursa (job #2785142) | Cod sursa (job #239179) | Cod sursa (job #120210)
Cod sursa(job #120210)
#include <cstring>
#include <cstdio>
#include <queue>
#define Tdim 10000001
#define Pdim 21
#define NumS 700001
using namespace std;
char T[Tdim];
char P[Pdim];
int Trie[NumS][3];
int Autm[NumS][3];
int Acc[NumS];
int NS;
int SOL;
struct elem
{
int t;
int muc;
int nod;
};
queue <elem> Q;
void baga_trie()
{
int st = 0;
int i, n, muc;
for(n=strlen(P), i=0; i<n; ++i)
{
muc = (int) P[i] - 'a';
if(Trie[st][muc])
st = Trie[st][muc];
else
{
Trie[st][muc] = ++ NS;
st = NS;
}
}
Acc[st] = 1;
}
void baga_atm(int t, int muc, int nod)
{
int b, i;
b = Autm[t][muc];
Autm[t][muc] = Trie[t][muc];
if(Acc[b]) Acc[nod] = 1;
for(i=0; i<3; ++i)
if(Trie[b][i]) Autm[nod][i] = Trie[b][i];
else Autm[nod][i] = Autm[b][i];
}
void bf()
{
int i;
elem e, new_e;
for(i=0; i<3; ++i)
if(Trie[0][i])
{
e.t = 0;
e.muc = i;
e.nod = Trie[0][i];
Q.push(e);
}
while(Q.empty() == false)
{
e = Q.front(); Q.pop();
baga_atm(e.t, e.muc, e.nod);
for(i=0; i<3; ++i)
if(Trie[e.nod][i])
{
new_e.t = e.nod;
new_e.muc = i;
new_e.nod = Trie[new_e.t][i];
Q.push(new_e);
}
}
}
int main()
{
freopen("abc2.in", "rt", stdin);
freopen("abc2.out", "wt", stdout);
scanf("%s", &T);
while(!feof(stdin))
{
scanf("%s", &P);
baga_trie();
}
bf();
int i, muc, n, st = 0;
for(n=strlen(T), i=0; i<n; ++i)
{
muc = (int) T[i] - 'a';
st = Autm[st][muc];
SOL += Acc[st];
}
printf("%d", SOL);
fclose(stdin);
fclose(stdout);
return 0;
}