Cod sursa(job #1845893)

Utilizator teoionescuIonescu Teodor teoionescu Data 11 ianuarie 2017 22:51:53
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<set>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");

const int MOD[] = {666013,int(1e9)+7};
const int Base = 37;
const int Nmax = 10000001;
char s[Nmax],cuv[21];
int n;
set<int> W[666013];

int main(){
    in.getline(s,Nmax);
    while(!in.eof()){
        in.getline(cuv,21);
        if(in.eof()) break;
        pair<int,int> has={0,0};
        n=strlen(cuv);
        for(int i=0;i<n;i++){
            has.first = (1LL*has.first*37 + cuv[i] - 'a')%MOD[0];
            has.second = (1LL*has.second*37 + cuv[i] - 'a')%MOD[1];
        }
        W[has.first].insert(has.second);
    }
    pair<int,int> pw={1,1};
    for(int i=1;i<n;i++){
        pw.first = (1LL*pw.first*37)%MOD[0];
        pw.second = (1LL*pw.second*37)%MOD[1];
    }
    int sz=strlen(s),ans=0;
    pair<int,int> has={0,0};
    for(int i=0;i<sz;i++){
        if(i>=n){
            if(W[has.first].find(has.second)!=W[has.first].end()) ans++;
            has.first = (1LL*MOD[0] + has.first - (1LL*(s[i-n]-'a')*pw.first)%MOD[0])%MOD[0];
            has.second = (1LL*MOD[1] + has.second - (1LL*(s[i-n]-'a')*pw.second)%MOD[1])%MOD[1];
        }
        has.first = (1LL*has.first*37 + s[i] - 'a')%MOD[0];
        has.second = (1LL*has.second*37 + s[i] - 'a')%MOD[1];
    }
    if(W[has.first].find(has.second)!=W[has.first].end()) ans++;
    out<<ans<<'\n';
    return 0;
}