Cod sursa(job #1880128)

Utilizator enacheionutEnache Ionut enacheionut Data 15 februarie 2017 15:30:11
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

#define KEY 666013
#define un unsigned
using namespace std;

ifstream f("abc2.in");
ofstream g("abc2.out");

vector < un int > mp[KEY];
string x;
int n,rez = 0;

void add(un int nr){

    int niv = nr%KEY;
    for(unsigned int i=0;i<mp[niv].size();++i)
        if(mp[niv][i] == nr)
            return;
    mp[niv].push_back(nr);
}
bool find(un int nr){

    int niv = nr%KEY;
    for(unsigned int i=0;i<mp[niv].size();++i)
        if(mp[niv][i] == nr)
            return true;
    return false;
}


void read(){

    getline(f,x);

    for(string a;getline(f,a);){

        n = a.size();
        un int nr = 0 ;
        for(int i=0;i<n;++i)
            nr = nr * 3 + a[i] - 'a';
        add(nr);
    }
}

void solve(){

    int len = x.size();
    un int nr = 0 , p = 1;

    for(int i=0;i<n;++i){

        nr = nr * 3 + x[i] - 'a';
        p = p * 3;
    }
    p/=3;
    rez+=find(nr);
    for(int i=n;i<len;++i){

        nr-=p*(x[i-n]-'a');
        nr= nr*3 + x[i] - 'a';
        rez+=find(nr);
    }
}

void write(){

    g<<rez;
}

int main()
{
    read();
    solve();
    write();
    return 0;
}