Cod sursa(job #2349726)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 20 februarie 2019 17:48:08
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

const int NMAX = 10000005;
const int MOD = 20029;

vector <int> v[MOD+5];
char a[NMAX];
char c[25];

bool caut(long long x)
{
    int aux=x%MOD;
    for(int i=0;i<v[aux].size();i++) if(v[aux][i]==x) return 1;
    return 0;
}

void hash_insert(long long x)
{
    int aux=x%MOD;
    if(caut(aux)==0)
    {
        v[aux].push_back(x);
    }
}

int main()
{
    fin >> (a+1);
    int asize=strlen(a+1);
    int n,baza;
    while(!fin.eof())
    {
        fin >> (c+1);
        n=strlen(c+1);
        baza=3;
        long long nr=0;
        for(int i=1;i<=n;i++) nr=nr*baza+(c[i]-'a'+1);
        hash_insert(nr);
    }
    long long putere=1;
    long long nr=0;
    for(int i=1;i<=n;i++)
    {
        nr=nr*baza+(a[i]-'a'+1);
        if(i==n) break;
        putere*=baza;
    }
    int rasp=0;
    if(caut(nr)==1) rasp++;
    for(int i=n+1;i<=asize;i++)
    {
        nr-=putere*(a[i-n]-'a'+1);
        nr*=baza;
        nr+=a[i]-'a'+1;
        if(caut(nr)==1) rasp++;
    }
    fout << rasp;
    return 0;
}