Pagini recente » Cod sursa (job #99726) | Cod sursa (job #470392) | Cod sursa (job #418135) | Cod sursa (job #1503423) | Cod sursa (job #237652)
Cod sursa(job #237652)
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[10000001],cuv[30];
long treila[30],val1,val2,hash1[50001],hash2[50001];
int nrap;
long h1(int m, char *s)
{
int i;
long prod=0;
for(i=0;i<m;i++)
prod=(prod+treila[m-i-1]*(s[i]-'a'));
return prod;
}
int caut_bin(long *vct,int el,long val)
{
int step = 1, rez = 1;
for (step = 1; step < el; step <<= 1);
for (; step; step >>= 1)
if (rez + step <= el && vct[rez + step] <= val)
rez += step;
if (vct[rez] == val)
return 1;
return 0;
}
int main()
{
int i,n,m,k;
FILE *f=fopen("abc2.in","r");
freopen("abc2.out","w",stdout);
fscanf(f,"%s\n",a);
fscanf(f,"%s\n",cuv);
n=strlen(a);
m=strlen(cuv);
treila[0]=1;
for(i=1;i<=m;i++)
treila[i]=treila[i-1]*3;
hash1[1]=h1(m,cuv);
k=1;
while(!feof(f))
{
fscanf(f,"%s",cuv);
hash1[++k]=h1(m,cuv);
}
std::sort(hash1+1,hash1+1+k);
val1=h1(m,a);
if(caut_bin(hash1,k,val1))
nrap++;
for(i=1;i<=n-m+1;i++)
{
val1=(val1-treila[m-1]*(a[i-1]-'a'))*3+a[i+m-1]-'a';
if(caut_bin(hash1,k,val1))
nrap++;
}
printf("%d",nrap);
fclose(f);
return 0;
}