Cod sursa(job #2107633)

Utilizator Andrei243Nitu Mandel Andrei Andrei243 Data 17 ianuarie 2018 16:35:37
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;

#define nr_karp 4

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

int marime_karp;
char sir[20001000];
vector<long long> cuvinte[85889];


long long rabin_karp(char* sir)
{
    long long rez=0;

    for(int i=marime_karp-1; i>=0; i--)
    {

        rez+=(int)(sir[i]-'a')*pow(nr_karp,marime_karp-i-1);


    }
    //cout<<sir<<' '<<rez<<'\n';
    return rez;

}

int hash1(char* sir)
{
    return rabin_karp(sir)%85889;


}

void adaugare(char* s)
{long long aux=rabin_karp(s);
    int aux_con=hash1(s);
    vector <long long>::iterator it;

    for(it=cuvinte[aux_con].begin(); it!=cuvinte[aux_con].end(); it++)
    {

       // if(strcmp(*it,s)==0)return;
if(*it==aux)return;
    }

    cuvinte[aux_con].push_back(rabin_karp(s));

}

bool cautare(char* s,int key)
{
long long aux=rabin_karp(s);
    vector <long long>::iterator it;
    for(it=cuvinte[key].begin(); it!=cuvinte[key].end(); it++)
    {
        //cout<<*it<<'\n';
        //if(strncmp(*it,s,marime_karp)==0)return 1;
    if(*it==aux)return 1;
    }

    return 0;
}


int main()
{
    in>>sir;


    while(1)
    {
        char s[25];
        in>>s;
        marime_karp=strlen(s);
        adaugare(s);
        if(in.eof())break;


    }
    int nr=0;
    int aux=strlen(sir);
    int cheie=hash1(sir);
    for(int i=0;/*aux-i>=marime_karp*/; i++)
    {
       // cout<<sir+i<<" "<<cheie<<'\n';
        if(cautare(sir+i,cheie))nr++;
        if(aux-i==marime_karp)break;
        cheie=cheie*nr_karp;
        cheie-=(sir[i]-'a')*pow(nr_karp,marime_karp);
        cheie+=sir[i+marime_karp]-'a';

    }
    out<<nr;
    return 0;
}