Cod sursa(job #530941)

Utilizator ChallengeMurtaza Alexandru Challenge Data 8 februarie 2011 18:12:08
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <cstring>
#include <list>

using namespace std;

const char InFile[]="abc2.in";
const char OutFile[]="abc2.out";
const int MaxN=10111000;
const int MaxL=21;
const int MOD=666017;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_el
{
	int cod;
	int count;
};

char str[MaxN],cuv[MaxL];
int N,L,sol,cpow,cod;
list<s_el> H[MOD];

inline void add(int key)
{
	int hash=key%MOD;
	list<s_el>::iterator it;
	for(it=H[hash].begin();it!=H[hash].end();++it)
	{
		if(it->cod==key)
		{
			break;
		}
	}
	if(it!=H[hash].end())
	{
		++it->count;
	}
	else
	{
		s_el el;
		el.cod=key;
		el.count=1;
		H[hash].push_back(el);
	}
}

inline int get(int key)
{
	int hash=key%MOD;
	list<s_el>::iterator it;
	for(it=H[hash].begin();it!=H[hash].end();++it)
	{
		if(it->cod==key)
		{
			break;
		}
	}
	if(it!=H[hash].end())
	{
		int t=it->count;
		it->count=0;
		return t;
	}
	return 0;
}

int main()
{
	fin>>str;
	fin>>cuv;
	N=strlen(str);
	L=strlen(cuv);
	cod=0;
	for(register int i=0;i<L;++i)
	{
		str[i]-='a';
		cod*=3;
		cod+=str[i];
	}
	cpow=1;
	for(register int i=1;i<L;++i)
	{
		cpow*=3;
	}
	add(cod);
	for(register int i=L;i<N;++i)
	{
		str[i]-='a';
		cod-=cpow*str[i-L];
		cod*=3;
		cod+=str[i];
		add(cod);
	}
	while(!fin.eof())
	{
		cod=0;
		for(register int i=0;i<L;++i)
		{
			cod*=3;
			cod+=cuv[i]-'a';
		}
		sol+=get(cod);
		fin>>cuv;
	}
	fin.close();

	fout<<sol;
	fout.close();
	return 0;
}