Cod sursa(job #98913)

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

#define maxN 21

using namespace std;

string A, B;

set <string> M;

int sol;
int Next[maxN];

void prefix()
{
    int i, q;

    memset(Next, 0, sizeof(Next));

    Next[0] = -1;

    for(i=1, q=-1; i<B.size(); ++i)
    {
        while(B[i] != B[q+1] && q >= 0)
            q = Next[q];

        if(B[i] == B[q+1]) ++ q;

        Next[i] = q;
    }
}

int check()
{
    int q, i, ret = 0;

    for(i=0, q=-1; i<A.size(); ++i)
    {
        while(A[i] != B[q+1] && q >= 0)
            q = Next[q];

        if(A[i] == B[q+1])
            ++ q;

        if(q == B.size()-1)
        {
            ++ ret;
            q = Next[q];
        }
    }

    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);
            prefix();

            sol += check();
        }
    }

    fout << sol;

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

    return 0;
}