Cod sursa(job #103367)

Utilizator damaDamaschin Mihai dama Data 15 noiembrie 2007 11:55:37
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.51 kb
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <vector>

using namespace std;

const int lenmax = 10000010;
const int modul = 100013;

char line[lenmax], cuv[24];
vector<pair<unsigned int, int> > v[modul];

int min(int a, int b)
{
	if(a < b)
	{
		return a;
	}
	return b;
}

unsigned int conv(char* c, int l)
{
	unsigned int res = 0;
	int i;

	for(i = 0; i < l; ++i)
	{
		res = 3 * res + c[i] - 'a';
	}
	return res;
}


int main()
{
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);

	int i, sol = 0, len, l, j, sz, ok;
	unsigned int aux = 0, temp, t = 1;

	fgets(line, lenmax, stdin);
	len = strlen(line) - 1;
	while(!isalpha(line[len - 1]))
	{
		--len;
	}
	fgets(cuv, 24, stdin);
	l = strlen(cuv) - 1;

	for(i = 1; i < l; ++i)
	{
		t *= 3;
	}
	
	for(i = 0; i < l; ++i)
	{
		aux = 3 * aux + line[i] - 'a';
	}

	for(i = l; i <= len; ++i)
	{
		//printf("%d\n", aux);
		temp = aux % modul;
		sz = v[temp].size();
		ok = 0;
		for(j = 0; j < sz; ++j)
		{
			if(v[temp][j].first == aux)
			{
				++v[temp][j].second;
				ok = 1;
				break;
			}
		}
		if(!ok)
		{
			v[temp].push_back(make_pair(aux, 1));
		}
		aux = (aux - t * (line[i - l] - 'a')) * 3 + line[i] - 'a';
	}
//	printf("\n");
	do
	{
		temp = conv(cuv, l);
		aux = temp % modul;
		sz = v[aux].size();
		//printf("%d\n",temp);
		for(i = 0; i < sz; ++i)
		{
			if(v[aux][i].first == temp)
			{
				sol += v[aux][i].second;
				v[aux][i].second = 0;
				break;
			}
		}
		fgets(cuv, 24, stdin);
	}
	while(!feof(stdin));

	printf("%d\n", sol);

	return 0;
}