Pagini recente » Cod sursa (job #54835) | Cod sursa (job #1887045) | Cod sursa (job #1956244) | Cod sursa (job #762533) | Cod sursa (job #2315266)
#include <fstream>
#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()
{
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin.getline(text,1000005);
v=new trie;
v->ch='\0';
while(fin.getline(cuv,25))
baga(cuv);
solve();
fout<<s;
return 0;
}