Cod sursa(job #1782959)

Utilizator Iustin48Ventaniuc Iustin Iustin48 Data 18 octombrie 2016 17:24:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda hash_excelenta Marime 1.82 kb
#include <fstream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
const int MOD=1000003;
char s[10000001],cuvant[21];
int lungime,lunsir,nr;
unsigned int putere;
unsigned int codificare;
vector<unsigned int> H[MOD];
int main()
{
    f>>s;
    lunsir=strlen(s);
    f>>cuvant;
    lungime=strlen(cuvant);
    putere=pow(3,lungime-1);
    for(int i=0;i<lungime;i++)
        codificare=codificare*3+(cuvant[i]-'a');
    H[codificare%MOD].push_back(codificare);
    codificare=0;
    while(f>>cuvant)
    {
        for(int i=0;i<lungime;i++)
            codificare=codificare*3+(cuvant[i]-'a');
        vector<unsigned int> :: iterator st=H[codificare%MOD].begin(),fn=H[codificare%MOD].end();
        int w=1;
        while(st!=fn&&w)
        {
            if(*st==codificare)
            {
                w=0;
                break;
            }
            st++;
        }
        if(w)
            H[codificare%MOD].push_back(codificare);
        codificare=0;
    }
    for(int j=0;j<lungime;++j)
        codificare=codificare*3+(s[j]-'a');
    vector<unsigned int> :: iterator st=H[codificare%MOD].begin(),fn=H[codificare%MOD].end();
    while(st!=fn)
    {
        if(*st==codificare)
        {
            nr++;
            break;
        }
        st++;
    }
    for(int i=lungime;i<lunsir;++i)
    {
        codificare%=putere;
        codificare=codificare*3+(s[i]-'a');
        vector<unsigned int> :: iterator st=H[codificare%MOD].begin(),fn=H[codificare%MOD].end();
        int w=1;
        while(st!=fn&&w)
        {
            if(*st==codificare)
            {
                nr++;
                w=0;
            }
            st++;
        }
    }
    g<<nr;
    g.close();
    return 0;
}