Cod sursa(job #2315266)

Utilizator dacianouaPapadia Mortala dacianoua Data 9 ianuarie 2019 17:46:09
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#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;
}