Pagini recente » Cod sursa (job #506870) | Cod sursa (job #2978321) | Cod sursa (job #1854890) | Cod sursa (job #1937352) | Cod sursa (job #100919)
Cod sursa(job #100919)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxl 1024*1024*10
#define prim 40939197
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 a)
{
a%=prim;
return pr[a];
}
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];
}
//return 0;
rez += gas2(w%prim);
long y = w%prim;
long p2 = p%prim;
for( long i = n; i < pp; ++i)
{
y = ( (prim*3 + y - p2 * text[i-n])*3 + text[i])%prim;
rez+=gas2(y);
}
printf("%ld\n",rez);
return 0;
}