Cod sursa(job #1766188)

Utilizator liviu23Liviu Andrei liviu23 Data 27 septembrie 2016 17:59:18
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <string.h>
#include <set>
#include <iostream>
#define B1 3
#define B2 7
#define M1 1000007
#define M2 1000009
using namespace std;

char s[10000005],s0[25];
int n,len,p1=1,p2=1;
set<int> h[M1];

int hashWord(char *s1,int b,int m) {
    int ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*b+(s1[i]-'a'))%m;
    return ans;
}

void init() {
    for(int i=0;i<len;i++)
        p1=(p1*B1)%M1, p2=(p2*B2)%M2;
}

int main()
{
    ifstream fin("abc2.in");
    ofstream fout("abc2.out");
    int h1,h2,ans=0;
    fin>>s;
    n=strlen(s);
    fin>>s0;
    len=strlen(s0);
    init();
    do {
        h1=hashWord(s0,B1,M1);
        h2=hashWord(s0,B2,M2);
        cout<<h1<<" "<<h2<<'\n';
        if(h[h1].find(h2)==h[h1].end())
            h[h1].insert(h2);
    } while(fin>>s0);
    h1=0,h2=0;
    for(int i=0;i<len;i++) {
        h1=(h1*B1+(s[i]-'a'))%M1;
        h2=(h2*B2+(s[i]-'a'))%M2;
    }
    if(h[h1].find(h2)!=h[h1].end())
        ans++;
    for(int i=len;i<n;i++) {
        h1=(h1*B1-p1*(s[i-len]-'a')+(s[i]-'a'))%M1;
        h2=(h2*B2-p2*(s[i-len]-'a')+(s[i]-'a'))%M2;
        if(h[h1].find(h2)!=h[h1].end())
            ans++;
    }
    fout<<ans;
    return 0;
}