Cod sursa(job #860642)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 20 ianuarie 2013 15:51:03
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#define mod1 100007
#define mod2 333337
#define Hmod 666013
using namespace std;
 
vector<int> H1[mod1], H2[mod2];
char text[10000000];
 
void add1(int x)
{
    const int m = x%mod1;
    vector<int>::iterator i=H1[m].begin(), stop=H1[m].end();
    while (i != stop)
    {
        if (*i == x)
            return;
        ++i;
    }
    H1[m].push_back(x);
}
 
void add2(int x)
{
    const int m = x%mod2;
    vector<int>::iterator i=H2[m].begin(), stop=H2[m].end();
    while (i != stop)
    {
        if (*i == x)
            return;
        ++i;
    }
    H2[m].push_back(x);
}

short search1(int x)
{
    const int m = x%mod1;
    vector<int>::iterator i=H1[m].begin(), stop=H1[m].end();
    while (i != stop)
    {
        if (*i == x)
            return 1;
        ++i;
    }
    return 0;
}
 
short search2(int x)
{
    const int m = x%mod2;
    vector<int>::iterator i=H2[m].begin(), stop=H2[m].end();
    while (i != stop)
    {
        if (*i == x)
            return 1;
        ++i;
    }
    return 0;
}

int hash(char *cuv, int l)
{
    int val=0, i;
    for (i=0; i<l; ++i)
        val = (val*3 + cuv[i]-'a')%Hmod;
    return val;
}   
 
int main()
{
    ifstream in("abc2.in"); ofstream out("abc2.out");
    char cuv[20]; 
    int i, l, cnt=0, val, n, g=1;
     
    in>>text>>cuv;
    l = strlen(cuv);
    val = hash(cuv, l);
	add1(val); add2(val);
    while (in>>cuv)
	{
		val = hash(cuv, l);
        add1(val); add2(val);
	}
     
    for (i=1; i<l; ++i)
        g = (g*3)%Hmod;
     
    val = hash(text, l);
    cnt += (search1(val) && search2(val));
    n = strlen(text);
     
    for (i=l; i<n; ++i)
    {
        val = ((val - ((text[i-l]-'a')*g)%Hmod + Hmod)*3 + text[i]-'a')%Hmod;
        cnt += (search1(val) && search2(val));
    }
     
    out<<cnt;
    return 0;
}