Cod sursa(job #955887)

Utilizator danalex97Dan H Alexandru danalex97 Data 1 iunie 2013 18:34:12
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <cstring>
#include <list>
using namespace std;

ifstream F("abc2.in");
ofstream G("abc2.out");

const int Mod = 666013;
const int Lmax = 10000010;
const int Wmax = 25;

typedef unsigned int ui;

int N,M,Out;
char A[Lmax];
char W[Wmax];
list<ui> H[Mod];

#define IT list<ui>::iterator

int in(ui what)
{
    int where = what%Mod;
    for (IT it=H[where].begin();it!=H[where].end();++it)
        if ( *it == what )
            return 1;
    return 0;
}

void insert(ui what)
{
    int where = what%Mod;
    H[where].push_back( what );
}

int main()
{
	F>>(A+1), N = strlen(A+1);
    F>>(W+1), M = strlen(W+1);

    ui what = 0, go = 1;
    for (int i=1;i<=M;++i) what = what * 3 + (ui)(W[i]-'a');
    if ( in(what) == 0 ) insert(what);

    for (ui what=0;F>>(W+1);what=0)
    {
        for (int i=1;i<=M;++i) what = what * 3 + (ui)(W[i]-'a');
        if ( in(what) == 0 ) insert(what);
    }

    if ( N < M )
    {
        G<<"0\n";
        return 0;
    }

    what = 0;
    for (int i=1;i<=M;++i)
    {
        what = what * 3 + (ui)(A[i]-'a');
        if ( i < M ) go *= 3;
    }
    Out += in(what);
    for (int i=M+1;i<=N;++i)
    {
        what -= go * ( A[i-M]-'a' );
        what = what * 3 + (ui)(A[i]-'a');
        Out += in(what);
    }

	G<<Out<<'\n';
}