Cod sursa(job #2107976)

Utilizator Andrei243Nitu Mandel Andrei Andrei243 Data 17 ianuarie 2018 20:28:15
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
//#include <iostream>
#include <fstream>
//#include <cmath>
#include <cstring>
#include <vector>
using namespace std;

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

int marime_karp;
char sir[10001000];
vector<unsigned int> cuvinte[25000];
unsigned int puteri[25];

unsigned int rabin_karp(char* sir)
{
    unsigned int rez=0;
    for(int i=marime_karp-1; i>=0; i--)
    {
        rez+=(int)(sir[i]-'a')*puteri[marime_karp-i-1];
    }

    return rez;
}

int cautare(unsigned int key)
{
    unsigned int aux=key;
    key=key%25000;
    vector <unsigned int>::iterator it;
    for(it=cuvinte[key].begin(); it!=cuvinte[key].end(); it++)
    {
        if(*it==aux)return 1;
    }

    return 0;
}

void adaugare(unsigned int aux)
{
    if(cautare(aux))return;
    cuvinte[aux%25000].push_back(aux);
}




void generare_puteri()
{
    puteri[0]=1;
    for(int i=1; i<25; i++)puteri[i]=puteri[i-1]*3;
}

int main()
{
    generare_puteri();
    in>>sir;
    char s[25];
    unsigned int aux_key;
    in>>s;
    marime_karp=strlen(s);
    aux_key=rabin_karp(s);
    adaugare(aux_key);
    while(1)
    {

        in>>s;

        aux_key=rabin_karp(s);
        adaugare(aux_key);
        if(in.eof())break;


    }
    long nr=0;
    int aux=strlen(sir);
    unsigned int cheie=rabin_karp(sir);
    for(int i=0; i<=aux-marime_karp; i++)
    {

        if(cautare(cheie))nr++;
        cheie*=3;
        cheie-=(unsigned int)(sir[i]-'a')*puteri[marime_karp];
        cheie+=sir[i+marime_karp]-'a';


    }
    out<<nr;
    return 0;
}