Cod sursa(job #1660769)

Utilizator ArkinyStoica Alex Arkiny Data 23 martie 2016 13:36:11
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<string>
#include<vector>
#include<string.h>
#include<iostream>
using namespace std;

ifstream in("abc2.in");
ofstream out("abc2.out");



char S[10000010];
char s1[22];
unsigned int pow1[20];

vector<unsigned int> hash1[600000];
#define MOD 500069
int main()
{
	in >> S;
	unsigned int p = 1;
	unsigned int S1 = 0;
	for (int i = 0; i < 20; ++i)
		pow1[i] = p,S1+=p, p *= 3;
	int ok = 0 , size = 0;
	while (in >> s1)
	{
		int i = 0;
		unsigned int s = 0;
		while (s1[i] != '\0')
			s += (s1[i] - 'a')*pow1[i], ++i;
		
		hash1[s%MOD].push_back(s);
		if (!ok)
			size = strlen(s1),ok=1;
	}

	int i = 0,nr=0;
	unsigned int s = 0;
	for (; i < size; ++i)
		s += (S[i] - 'a')*pow1[i];

	int key = s%MOD;

	for (int i = 0; i < hash1[key].size(); ++i)
		if (hash1[key][i] == s)
		{
			++nr;
			break;
		}

	while (S[i] != '\0')
	{
		s /= 3;
		s += (S[i]-'a')*pow1[size-1];
		key = s%MOD;
		for (int i = 0; i < hash1[key].size(); ++i)
			if (hash1[key][i] == s)
			{
				++nr;
				break;
			}
		++i;
	}
	
	out << nr;
	
	
	return 0;
}