Cod sursa(job #860637)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 20 ianuarie 2013 15:38:35
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#define mod 100007
#define Hmod 666013
using namespace std;

vector<int> H[mod];
char text[10000000];

void add(int x)
{
	const int m = x%mod;
	vector<int>::iterator i=H[m].begin(), stop=H[m].end();
	while (i != stop)
	{
		if (*i == x)
			return;
		++i;
	}
	H[m].push_back(x);
}

short search(int x)
{
	const int m = x%mod;
	vector<int>::iterator i=H[m].begin(), stop=H[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);
	add(hash(cuv, l));
	while (in>>cuv)
		add(hash(cuv, l));
	
	for (i=1; i<l; ++i)
		g = (g*3)%Hmod;
	
	val = hash(text, l);
	cnt += search(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 += search(val);
	}
	
	out<<cnt;
	return 0;
}