Cod sursa(job #98888)

Utilizator raula_sanChis Raoul raula_san Data 10 noiembrie 2007 18:25:26
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.15 kb
#include <fstream>
#include <string>
#include <set>

#define maxN 21

using namespace std;

string A, B;

set <string> M;

int sol, ns;
int atm[maxN][3];

void baga_automat()
{
    memset(atm[0], 0, sizeof(0));

    int i, j, c, st;

    st = 0;
    ns = 0;

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

        ++ ns;

        if(atm[st][c] == st)
            atm[ns][c] = ns;
        else
            atm[ns][c] = atm[st][c];

        atm[st][c] = ns;

        for(j=0; j<3; ++j)
            if(j != c)
            {
                atm[ns][j] = atm[st][j];
            }

       st = ns;
    }
}

int check()
{
    int s, c, i, ret;

    s = 0;
    ret = 0;

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

    return ret;
}

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

    fin >> A;

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

        if(M.find(B) == M.end())
        {
            M.insert(B);
            baga_automat();

            sol += check();
        }
    }

    fout << sol;

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

    return 0;
}