Cod sursa(job #102090)

Utilizator blasterzMircea Dima blasterz Data 13 noiembrie 2007 23:46:15
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.53 kb
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define maxn 60003
#include <set>
#include <vector>
#include <bitset>
using namespace std;

char T[10000001];
int n;
//bool used[10000001];
vector<long long>H[maxn+2];
long long A[50001];
int N,CNT;
inline int insrt(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=4*t+x[i]-'a'+1;
	//if(A[N]!=t) A[++N]=t;
	int h=(int)(t%maxn);
	H[h].push_back(t);
}


	

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);
		insrt(x);
	}
	//sort(A+1, A+N+1);
	//for(CNT=1; CNT<=N; CNT<<=1);
}
/*
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;
}
*/

inline int fnd(long long v)
{
	int i, cnt;
	for(i=1, cnt=(CNT); cnt ; cnt>>=1)
		if(i+cnt<=N)
			if(A[i+cnt]<=v) i+=cnt;
	if(A[i]==v)return 1;
	return 0;
}




int main()
{
	read();
	freopen("abc2.out","w",stdout);
	int i, j;
	long long p;
	int nr=0, ok,h;
	vector<long long>::iterator it;
	for(i=0;i<n;++i)
	//if(!used[i])
	{
		p=0;
		for(j=i;j<i+20;++j)
		{
			p=p*4+T[j]-'a'+1;
		//	printf("%lld\n", p);
			
			ok=0;
			h=(int)(p%maxn);
			
			for(it=H[h].begin();it!=H[h].end();++it)
				if(*it==p) { ok=1; break;}
			if(ok)
			{
				++nr;
			//	used[i]=1;
				break;
			}
		}
	}
	printf("%d\n", nr);
	return 0;
}