Cod sursa(job #2515005)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 27 decembrie 2019 16:16:03
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <cstring>
#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;

int fr1[40105];
int fr2[319997];

int main()
{
    f.getline(s, LMAX);
    n=strlen(s);

    Hash s1pHash{31, 40099}, s2pHash{31, 40099};
    Hash s1oHash{53, 319993}, s2oHash{53, 319993};

    while(f.getline(cuv, LLMAX)){
        m = strlen(cuv);
        s1pHash.init(s, m);
        s1oHash.init(s, m);
        s2pHash.init(cuv, m);
        s2oHash.init(cuv, m);
        if(fr1[s2pHash.hashh] == 1 && fr2[s2oHash.hashh]==1)
            continue;
        fr1[s2pHash.hashh] = 1;
        fr2[s2oHash.hashh] = 1;
        if(s1pHash.hashh == s2pHash.hashh && s1oHash.hashh == s2oHash.hashh)
            nr++;
        for(long long i=m; i<n; i++){
            s1pHash.roll(s[i-m], s[i]);
            s1oHash.roll(s[i-m], s[i]);
            if(s1pHash.hashh == s2pHash.hashh && s1oHash.hashh == s2oHash.hashh)
                nr++;
        }
    }
    g<<nr;
    return 0;
}