Pagini recente » Cod sursa (job #1951791) | Cod sursa (job #1648288) | Cod sursa (job #415223) | Cod sursa (job #2884446) | Cod sursa (job #170482)
Cod sursa(job #170482)
# include <stdio.h>
# include <string>
# include <fstream>
using namespace std;
# define input "abc2.in"
# define output "abc2.out"
# define max 10000001
# define maxm 50001
char s[max],t[21];
long long a[maxm],x;
long long p[21];
int l,j,sz;
int n,i,rez,m;
int cauta(long long x)
{
int i,e;
for(e = 1;e < m;e <<= 1);
for(i = 0;e ;e >>= 1)
if(i + e <= m && a[i+e] <= x) i+= e;
if(a[i] == x)
return 1;
return 0;
}
int main()
{
FILE * IN = fopen(input,"r");
FILE * OUT = fopen(output,"w");
fgets(s,max,IN);
fgets(t,20,IN);
n = strlen(t) - 1;
p[n-1] = 1;
for(i=n-2;i >= 0 ;i--)
p[i] = p[i+1] * 3;
x = 0;
for(i=0;i<n;i++)
x+=p[i]*(t[i]-'a');
a[++m] = x;
while(fgets(t,20,IN))
{
x = 0;
for(i=0;i<n;i++)
x+=p[i]*(t[i]-'a');
a[++m] = x;
}
sort(a+1,a+m+1);
sz = strlen(s);
x = 0;
for(i=0;i<n;i++)
x+=p[i]*(s[i]-'a');
if(cauta(x))
rez++;
for(i = n;i < sz; i++)
{
x-=(s[i-n]-'a') * p[0];
x*=3;
x+= s[i] -'a';
if(cauta(x))
rez++;
}
fprintf(OUT,"%d",rez);
return 0;
}