Cod sursa(job #1482548)

Utilizator dnprxDan Pracsiu dnprx Data 7 septembrie 2015 15:00:10
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
#define modulo 370003

using namespace std;

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

void Init()
{
    int i;
    p3[1] = 1;
    for (i = 2; i <= 20; i++)
        p3[i] = p3[i - 1] * 3;
}

inline void Adauga(long long 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(long long 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;
    long long 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 + (t[i] - 'a') * p3[i + 1];
    Adauga(aux);
    while(fin >> t)
    {
        aux = 0;
        for(i = 0; i < lung; i++)
            aux = aux + (t[i] - 'a') * p3[i + 1];
        Adauga(aux);
    }
    fin.close();
}

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

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