Cod sursa(job #2515014)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 27 decembrie 2019 16:54:22
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <cstring>
#include <vector>
#define LMAX 10000005
#define LLMAX 25
using namespace std;

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

struct Hash{
    long long n, m, power, hashh;
    void init(char *s, long long len){
        power = 1;
        hashh = 0;
        for(long long i=len-1; i>=0; i--){
            hashh = (hashh + (1LL*power*s[i])%m)%m;
            if(i) power = (power*n)%m;
        }
    }
   void roll(char toRemove, char toAdd)
    {
        hashh=(((hashh-(1LL*toRemove*power)%m+m)*n)%m+toAdd)%m;
    }
};
char s[LMAX];
int n;
char cuv[LLMAX];
int m;

int nr=0;

struct hc{
    long long h1;
    long long h2;
};

vector<hc>hashcuvinte;

int main()
{
    f.getline(s, LMAX);
    n=strlen(s);
    Hash h1{31, 40099};
    Hash h2{53, 319993};
    while(f>>cuv){
        m = strlen(cuv);
        h1.init(cuv, m);
        h2.init(cuv, m);
        int ok = 1;
        for(auto &v:hashcuvinte)
            if(v.h1 == h1.hashh && v.h2 == h2.hashh){
                 ok = 0;
                 break;
             }
        if(ok == 1)
            hashcuvinte.push_back({h1.hashh, h2.hashh});

    }

    int nr=0;
    h1.init(s, m);
    h2.init(s, m);
    for(auto &v:hashcuvinte)
        if(v.h1 == h1.hashh && v.h2 == h2.hashh)
            nr++;
    //g<<nr;
    for(int i = m; i<n; i++){
        h1.roll(s[i-m],s[i]);
        h2.roll(s[i-m],s[i]);
        for(auto &v:hashcuvinte)
            if(v.h1 == h1.hashh && v.h2 == h2.hashh)
                nr++;
    }
    g<<nr;
    return 0;
}