Pagini recente » Cod sursa (job #1260631) | Cod sursa (job #2327804) | Cod sursa (job #3219805) | Cod sursa (job #761425) | Cod sursa (job #2315261)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <deque>
using namespace std;
FILE *fin,*fout;
char text[1000005],cuv[25];
int s=0;
struct trie
{
char ch;
bool cuv=0;
trie *copii[3]={0},*fail=0;
}*v;
void baga(char *c)
{
trie *d=v;
for(;d->copii[c[0]-'\0'-97] && *c!='\0';d=d->copii[c[0]-'\0'-97],c++);
if(c)
for(;*c!='\0';d->copii[c[0]-'\0'-97]=new trie,d->copii[c[0]-'\0'-97]->ch=c[0],d=d->copii[c[0]-'\0'-97],c++);
d->cuv=1;
}
void build_link()
{
deque<trie*> q;
trie *d,*f;
v->fail=v;
for(int i=0;i<3;i++)
if(v->copii[i])
v->copii[i]->fail=v,q.push_back(v->copii[i]);
while(!q.empty())
{
d=q.front();
q.pop_front();
for(int i=0;i<3;i++)
if(d->copii[i])
{
f=d->fail;
while(f!=v && !f->copii[i])
f=f->fail;
if(!f->copii[i])
d->copii[i]->fail=v;
else d->copii[i]->fail=f->copii[i];
q.push_back(d->copii[i]);
}
}
}
void solve()
{
build_link();
trie* d=v;
int length=strlen(text);
for(int i=0;i<length;i++)
{
if(d->cuv)
++s;
//base cases
while(!d->copii[text[i]-'\0'-97] && d!=v)
d=d->fail;
if(!d->copii[text[i]-'\0'-97])
continue;
d=d->copii[text[i]-'\0'-97];
}
}
int main()
{
fin=fopen("abc2.in","r");
fout=fopen("abc2.out","w");
fscanf(fin,"%s",&text);
v=new trie;
v->ch='\0';
while(fscanf(fin,"%s",&cuv)!=EOF)
baga(cuv);
solve();
fprintf(fout,"%d",s);
return 0;
}