Cod sursa(job #1766255)

Utilizator liviu23Liviu Andrei liviu23 Data 27 septembrie 2016 19:17:42
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <string.h>
#include <vector>
#define M 666013
using namespace std;

char s[10000010],c[30];
unsigned n,len,p[30],h,ans;
vector<unsigned int> t[M];

bool findHash(unsigned h0) {
    unsigned val=h0%M,s=t[val].size();
    for(int i=0;i<s;i++)
        if(t[val][i]==h0)
            return true;
    return false;
}

int main()
{
    ifstream fin("abc2.in");
    ofstream fout("abc2.out");
    p[0]=1;
    for(unsigned i=1;i<=20;i++)
        p[i]=p[i-1]*3;
    fin>>s;
    n=strlen(s);
    while(fin>>c) {
        if(!len) len=strlen(c);
        h=0;
        for(unsigned i=0;i<len;i++)
            h+=p[i]*(c[i]-'a');
        t[h%M].push_back(h);
    }
    h=0;
    for(unsigned i=0;i<len;i++)
        h+=p[i]*(s[i]-'a');
    if(findHash(h))
        ans++;
    for(unsigned i=len;i<n;i++) {
        h/=3;
        h+=p[len-1]*(s[i]-'a');
        if(findHash(h))
            ans++;
    }
    fout<<ans;
    return 0;
}