Pagini recente » Cod sursa (job #803579) | Cod sursa (job #663386) | Cod sursa (job #1899294) | Cod sursa (job #855520) | Cod sursa (job #111720)
Cod sursa(job #111720)
#include<stdio.h>
#define Tm 10000001
#define Nm 1000000
#define Sigma 3
#define Wm 21
char T[Tm],Match[Nm];
int Q[Nm],Trie[Sigma][Nm],D[Sigma][Nm],Fail[Nm],n,ans;
void read_and_insert()
{
char W[Wm];
int i,q;
freopen("abc2.in","r",stdin);
gets(T);
while(scanf("%s",W)==1)
{
for(q=i=0;W[i];++i)
{
if(!Trie[W[i]-'a'][q])
Trie[W[i]-'a'][q]=++n;
q=Trie[W[i]-'a'][q];
}
Match[q]=1;
}
}
void construct_automaton()
{
int l,r,x,i,y,q,j;
Q[l=r=0]=0;
for(i=0;i<Sigma;++i)
if(Trie[i][0])
D[i][0]=Trie[i][0];
else
D[i][0]=0;
while(l<=r)
{
x=Q[l++];
if(Match[Fail[x]])
Match[x]=1;
for(i=0;i<Sigma;++i)
{
y=Trie[i][x];
if(!y)
continue;
Q[++r]=y;
q=Fail[x];
while(q && !Trie[i][q])
q=Fail[q];
if(Trie[i][q] && Trie[i][q]!=y)
Fail[y]=Trie[i][q];
else
Fail[y]=0;
for(j=0;j<Sigma;++j)
if(Trie[j][y])
D[j][y]=Trie[j][y];
else
D[j][y]=D[j][Fail[y]];
}
}
}
void match()
{
int i,q;
for(q=i=0;T[i];++i)
{
q=D[T[i]-'a'][q];
ans+=Match[q];
}
}
void write()
{
freopen("abc2.out","w",stdout);
printf("%d\n",ans);
}
int main()
{
read_and_insert();
construct_automaton();
match();
write();
return 0;
}