Cod sursa(job #2315261)

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