Cod sursa(job #916301)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 16 martie 2013 12:07:51
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MOD 666013

using namespace std;

int n, m;
int sol;
char a[10000010];
vector <unsigned int> H[666013];

inline void Read()
{
    ifstream f ("abc2.in");
    f>>(a+1);
    n = strlen(a+1);
    char ch[25];
    unsigned int nr, put = 1;
    int i;
    f>>(ch+1);
    m = strlen(ch+1); // put = 3^(m-1);
    for (i=1; i<m; i++)
        put = put*3;
    nr = 0;
    for (i=1; i<=m; i++)
        nr = nr*3 + (ch[i] - 'a');
    H[nr%MOD].push_back(nr);
    while (f>>(ch+1))
    {
        nr = 0;
        for (i=1; i<=m; i++)
            nr = nr*3 + (ch[i] - 'a');
        H[nr%MOD].push_back(nr);
    }
    f.close();
}

inline void Solve()
{
    unsigned int nr, put = 1, poz;
    bool gasit;
    vector <unsigned int>::iterator it, final;
    int i;
    // put = 3^(m-1);
    for (i=1; i<m; i++)
        put = put*3;

    nr = 0;
    for (i=1; i<=m; i++)
        nr = nr*3 + (a[i] - 'a');
    poz = nr%MOD;
    for (gasit = false, it = H[poz].begin(), final = H[poz].end(); it!=final && !gasit; it++)
        if (*it == nr)
            gasit = true;
    sol+=gasit;

    for (; i<=n; i++)
    {
        nr = (nr - put*(a[i-m]-'a'))*3 + (a[i] - 'a');
        poz = nr%MOD;
        for (gasit = false, it = H[poz].begin(), final = H[poz].end(); it!=final && !gasit; it++)
            if (*it == nr)
                gasit = true;
        sol += gasit;
    }
}

inline void Write()
{
    FILE*g = fopen("abc2.out", "w");
    fprintf(g, "%d\n", sol);
    fclose(g);
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}