Cod sursa(job #1518843)

Utilizator ipus1Stefan Enescu ipus1 Data 6 noiembrie 2015 15:17:43
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char v[10000001],v2[21];
long long vec[50001];
int main ()
{freopen ("abc2.in","r",stdin);
freopen ("abc2.out","w",stdout);
int n,i,k,p,c1,c2,l,s=0,p4;
long long x;
scanf("%s",&v);
n=strlen(v);
p=0;
while(scanf("%s",&v2)!=EOF)
	{x=0;
	if(p==0)
		k=strlen(v2);
	for(i=0;i<k;i++)
		x=x*4+v2[i]-'a'+1;
	p++;
	vec[p]=x;
	}
sort(vec+1,vec+p+1);
x=0;
for(i=0;i<k;i++)
	x=x*4+v[i]-'a'+1;
c1=1;
c2=p;
while(c1<=c2)
	{l=(c1+c2)/2;
	if(vec[l]==x)
		{c1=c2+1;
		s++;
		}
	else
		if(x<vec[l])
			c2=l-1;
		else
			c1=l+1;
	}
p4=1;
for(i=1;i<k;i++)
	p4*=4;
for(i=k;i<n;i++)
	{x=(x-(v[i-k]-'a'+1)*p4)*4+v[i]-'a'+1;
	c1=1;
	c2=p;
	while(c1<=c2)
		{l=(c1+c2)/2;
		if(vec[l]==x)
			{c1=c2+1;
			s++;
			}
		else
			if(x<vec[l])
				c2=l-1;
			else
				c1=l+1;
		}
	}
printf("%d",s);
return 0;
}