Cod sursa(job #1482991)

Utilizator aaron72Armand Ioan Anusca Popa aaron72 Data 8 septembrie 2015 14:26:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
#define modulo 370003
#define X 3
using namespace std;

vector <int> h[modulo+1];
char s[10000005];
int lung;

inline void Adauga(int x)
{
    int r;
    unsigned i;
    r=x%modulo;
    for(i=0;i<h[r].size();i++)
        if(h[r][i]==x) return;
    h[r].push_back(x);
}

inline int Cautare(int x)
{
    int r;
    unsigned i;
    r=x%modulo;
    for(i=0;i<h[r].size();i++)
        if(h[r][i]==x) return 1;
    return 0;
}

inline void Citire()
{
    int i;
    unsigned int aux;
    char t[25];
    ifstream fin("abc2.in");
    fin>>s;
    fin>>t;
    lung=strlen(t);
    aux=0;
    for(i=0;i<lung;i++)
        aux=aux*X+(t[i]-'a');
    Adauga(aux);
    while(fin>>t)
    {
        aux=0;
        for(i=0;i<lung;i++)
            aux=aux*X+(t[i]-'a');
        Adauga(aux);
    }
    fin.close();
}

inline void Rezolva()
{
    unsigned int aux,L=1;
    int i,cnt;
    for(i=1;i<lung;i++)
        L*=X;
    aux=0;
    for(i=0;i<lung;i++)
        aux=aux*X+(s[i]-'a');
    cnt=0;
    cnt+=Cautare(aux);
    for(i=lung;s[i];i++)
    {
        aux=(aux-L*(s[i-lung]-'a'))*X + (s[i]-'a');
        cnt+=Cautare(aux);
    }
    ofstream fout("abc2.out");
    fout<<cnt<<"\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolva();
    return 0;
}