Cod sursa(job #102860)

Utilizator blasterzMircea Dima blasterz Data 14 noiembrie 2007 19:05:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.3 kb
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define maxn 100003
#define maxlog 17
#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;
bool H[maxn][maxlog];
int MAX;

inline int insrt(char x[])
{
	int n=0;
	while(x[n]>='a' && x[n]<='c') ++n;
	if(MAX<n) MAX=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 h1=(int)(t%maxn);
	int h2=(int)(t%maxlog);
	H[h1][h2]=1;
	//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);
	}
	
	/*
	for(i=0;i<maxn;++i) sort(H[i].begin(), H[i].end());
	
	for(i=0;i<maxn;++i)
	if(H[i].size())
	{
		int tt[10], nt=1;
		tt[1]=H[i][0];	
		for(j=1;j<H[i].size();++j)
			if(H[i][j]==H[i][j-1]);
			else tt[++nt]=H[i][j];
		H[i].clear();
		for(j=1;j<=nt;++j) H[i].push_back(tt[j]);
	}

	
	sort(A+1, A+N+1);
	
	long long ax[50001];
	int nx=1;
	ax[1]=A[1];
	for(i=2;i<=N;++i)
		if(A[i]!=A[i-1]) ax[++nx]=A[i];
	for(i=1;i<=nx;++i) A[i]=ax[i];
	N=nx;
	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,h1,h2;
	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+MAX;++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(binary_search(H[h].begin(), H[h].end(), p))
			h1=(int)p%maxn;
			h2=(int)p%maxlog;
			//printf("%d %d\n", h1, h2);
			if(H[h1][h2])
			{
				++nr;
			//	used[i]=1;
				break;
			}
		}
	}
	printf("%d\n", nr);
		//for(i=0;i<maxn;++i) if(H[i].size()>1) printf("da\n");
	return 0;
}