Cod sursa(job #612732)

Utilizator maritimCristian Lambru maritim Data 9 septembrie 2011 22:03:02
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define MaxN 10000010
#define ll long long
#define MaxC 50100

ll A[MaxC];
char S[MaxN];
int ln,NR,MAX,LN;

ll BazaTrei(char A[])
{
	ll a = 1;
	for(int i=0;i<ln-1;i++)
		a = a*3 + A[i]-'a';
	return a;
}

void citire(void)
{
	char a[27];
	FILE *f = fopen("abc2.in","r");
	
	fgets(S,sizeof(S),f);
	while(!feof(f))
	{
		fgets(a,sizeof(a),f);
		ln = strlen(a);
		A[++NR] = BazaTrei(a);
	}
	
	fclose(f);
}

int bs(int li,int ls,int a)
{
	if(li <= ls)
		if(A[(li+ls)/2] == a)
			return 1;
		else if(A[(li+ls)/2] < a)
			return bs((li+ls)/2+1,ls,a);
		else
			return bs(li, (li+ls)/2-1, a);
	return 0;
}

void solve(void)
{
	LN = strlen(S);
	for(int i=0;i<=LN-ln;i++)
	{
		int a = 1;
		for(int j=0;j<ln-1;j++)
			a = a*3 + S[i+j]-'a';
		MAX += bs(1,NR-1,a);
	}
}

int main()
{
	FILE *g = fopen("abc2.out","w");
	
	citire();
	sort(A+1,A+NR);
	solve();
	fprintf(g,"%d ",MAX);
	
	fclose(g);
	return 0;
}