Pagini recente » Cod sursa (job #2549469) | Cod sursa (job #2557166) | Cod sursa (job #2187936) | Cod sursa (job #1606990) | Cod sursa (job #100892)
Cod sursa(job #100892)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxl 1024*1024*10
#define prim 10939197
#define prim2 10939197
long n,cat = 0;
char text[maxl];
char pr[prim];
long long s[50001];
void baga(char *sir )
{
++cat;
for(long i = 0; i < n; ++i)
s[cat] = s[cat]*3 + sir[i]-'a';
}
int strcmpa(const void *a, const void *b)
{
return *(long *) a - * ( long *)b;
}
int gas(long long a)
{
long st = 1;
long dr = cat;
long mij;
while( st != dr)
{
mij = (st+dr)>>1;
//if( s[mij] == a) return 1;
if( s[mij] < a)
st = mij+1;
else dr = mij;
}
if( s[st] == a) return 1;
return 0;
}
void baga2(char *a)
{
long long w=0;
for( long i = 0; i < n ; ++i)
{
w = w*3 + a[i]-'a';
}
pr[w%prim] = 1;
}
int gas2(long long a)
{
return pr[a%prim];
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
char sir[32];
scanf("%s",text);
long ok = 0;
while( scanf("%s",sir) == 1)
{
if( !ok)
n = strlen(sir);
baga2(sir);
ok = 1;
}
qsort(s+1,cat,sizeof(s[0]),strcmpa);
long long w = 0, p = 1;
long pp = strlen(text);
for( long i = 0; i < pp; ++i)
text[i]-='a';
long rez =0;
for ( long i = 0; i < n-1; ++i)
p*=3;
if( n > p)
{
printf("0\n");
return 0;
}
for( long i = 0; i < n ; ++i)
{
w = w*3 + text[i];
}
rez += gas2(w);
for( long i = n; i < pp; ++i)
{
w = (w- p * text[i-n])*3 + text[i];
rez+=gas2(w);
}
printf("%ld\n",rez);
return 0;
}