Cod sursa(job #1766204)

Utilizator liviu23Liviu Andrei liviu23 Data 27 septembrie 2016 18:14:46
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <string.h>
#include <set>
#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%m)*b)%m+(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);
        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%M1)*B1)%M1+(s[i]-'a'))%M1;
        h2=(((h2%M1)*B2)%M1+(s[i]-'a'))%M2;
    }
    if(h[h1].find(h2)!=h[h1].end())
        ans++;
    for(int i=len;i<n;i++) {
        h1=(((h1%M1)*B1)%M1-p1*(s[i-len]-'a')+M1+(s[i]-'a'))%M1;
        h2=(((h2%M1)*B2)%M2-p2*(s[i-len]-'a')+M2+(s[i]-'a'))%M2;
        if(h[h1].find(h2)!=h[h1].end())
            ans++;
    }
    fout<<ans;
    return 0;
}