Cod sursa(job #2515012)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 27 decembrie 2019 16:45:55
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 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;

int fr1[40105];

int main()
{
    f.getline(s, LMAX);
    n=strlen(s);
    Hash h1{31, 40099};

    while(f>>cuv){
        m = strlen(cuv);
        h1.init(cuv, m);
        fr1[h1.hashh]=1;
    }

    int nr=0;
    h1.init(s, m);
    if(fr1[h1.hashh] == 1)
        nr++;
    //g<<nr;
    for(int i = m; i<n; i++){
        h1.roll(s[i-m],s[i]);
        if(fr1[h1.hashh] == 1)
            nr++;
    }
    g<<nr;
    return 0;
}