Cod sursa(job #102037)

Utilizator blasterzMircea Dima blasterz Data 13 noiembrie 2007 23:12:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.05 kb
#include <cstdio>
#include <string>
#define maxn 600003

char T[10000001];
int n;
bool used[10000001];

struct nod { long long v; nod *n;};

nod *H[maxn];


inline void insert(char x[])
{
	int n=0;
	while(x[n]>='a' && x[n]<='c') ++n;
	long long t=0;
	for(int i=0;i<n;++i)
		t=5*t+x[i]-'a'+1;
	int h=(int)(t%maxn);
	nod *p=new nod;
	p->v=t;
	p->n=H[h];
	H[h]=p;
}


	

void read()
{
	int i, j;
	freopen("abc2.in","r",stdin);
	gets(T);
	n=0;
	while(T[n]>='a' && T[n]<='c') ++n;
	int nr=0;
	
	while(!feof(stdin))
	{
		char x[32];
		gets(x);
		insert(x);
	}
}

inline int find(long long v)
{
	int h=(int)(v%maxn);
	for(nod *p=H[h]; p ; p=p->n)
		if(p->v==v)return 1;
	return 0;
}


int main()
{
	read();
	freopen("abc2.out","w",stdout);
	int i, j;
	long long p;
	int nr=0;
	for(i=0;i<n;++i)
	if(!used[i])
	{
		p=0;
		for(j=i;j<i+21;++j)
		{
			p=p*5+T[j]-'a'+1;
		//	printf("%lld\n", p);
			if(find(p) && !used[i])
			{
				++nr;
				used[i]=1;
				break;
			}
		}
	}
	printf("%d\n", nr);
	return 0;
}