Pagini recente » Cod sursa (job #2678511) | Cod sursa (job #495233) | Cod sursa (job #576926) | Cod sursa (job #1779100) | Cod sursa (job #111681)
Cod sursa(job #111681)
#include<stdio.h>
#define Tm 10100001
#define Nm (1<<20)
#define Sigma 3
#define Wm 21
char T[Tm],Match[Nm];
int Q[Nm],Trie[4][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=0,r=-1,x,i,y,q;
for(i=0;i<Sigma;++i)
{
y=Trie[i][0];
if(!y)
continue;
Q[++r]=y;
Fail[y]=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])
Fail[y]=Trie[i][q];
else
Fail[y]=0;
}
}
}
void match()
{
int i,q;
for(q=i=0;T[i];++i)
{
while(q && !Trie[T[i]-'a'][q])
q=Fail[q];
if(Trie[T[i]-'a'][q])
q=Trie[T[i]-'a'][q];
else
q=0;
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;
}