Cod sursa(job #99118)

Utilizator raula_sanChis Raoul raula_san Data 10 noiembrie 2007 21:27:51
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.73 kb
#include <fstream>
#include <bitset>
#include <string>
#include <queue>

#define maxS 500000

using namespace std;

string A, B;

bitset <maxS> acc;

int sol, ns;
int trie[maxS][3], atm[maxS][3];

struct elem
{
    int st;
    int m;
    int t;
};

queue <elem> Q;

void baga_trie()
{
    int i, c, n, s = 0;

    n = B.size();
    
    for(i=0; i<n; ++i)
    {
        c = (int) B[i] - 'a';

        if(!trie[s][c])
        {
            trie[s][c] = ++ ns;
            s = ns;
        }
        else
            s = trie[s][c];
    }

    acc[s] = 1;
}

void baga_atm(int t, int m, int nod)
{
    int b, i;

    b = atm[t][m];
    atm[t][m] = trie[t][m];

    if(acc[b]) acc[nod] = 1;

    for(i=0; i<3; ++i)
        if(trie[b][i]) atm[nod][i] = trie[b][i];
        else atm[nod][i] = atm[b][i];
}

void bf()
{
    int i, j;

    elem x;

    for(i=0; i<3; ++i)
        if(trie[0][i])
        {
            x.st = 0;
            x.m = i;
            x.t = trie[0][i];

            Q.push(x);
        }

    while(Q.empty() == false)
    {
        x = Q.front();
        Q.pop();

        baga_atm(x.st, x.m, x.t);

        for(j=0; j<3; ++j)
            if(trie[x.t][j])
            {
                elem nx;

                nx.st = x.t;
                nx.m = j;
                nx.t = trie[x.t][j];

                Q.push(nx);
            }
    }
}

int main()
{
    ifstream fin("abc2.in");
    ofstream fout("abc2.out");

    fin >> A;

    while(!fin.eof())
    {
        fin >> B;

        baga_trie();
    }

    bf();

    int i, s, n, c;

    n = A.size();
    s = 0;
    
    for(i=0; i<n; ++i)
    {
        c = (int) A[i] - 'a';

        s = atm[s][c];

        if(acc[s]) ++ sol;
    }

    fout << sol;

    fin.close();
    fout.close();

    return 0;
}