Cod sursa(job #919562)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 18:51:26
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 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);
    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()
{
    if (n<m)
    {
        ofstream g("abc2.out");
        g<<"0\n";
        g.close();
        return ;
    }
    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 (it = H[poz].begin(), final = H[poz].end(); it!=final; it++)
            if (*it == nr)
                sol++, it = final - 1;
    }
 
    ofstream g("abc2.out");
    g<<sol<<"\n";
    g.close();
}
 
int main()
{
    Read();
    Solve();
    return 0;
}