Pagini recente » Cod sursa (job #2327862) | Cod sursa (job #3285785) | Cod sursa (job #714070) | Cod sursa (job #1249189) | Cod sursa (job #104569)
Cod sursa(job #104569)
#include <stdio.h>
#include <stdlib.h>
#define L_MAX 10000001
#define M_MAX 50001
#define HASH 666013
char v[L_MAX],hash[HASH];
unsigned int a[M_MAX],b[M_MAX],k,ultim;
int L,m,n,s;
int compare(const void *b, const void *c){
return (*(unsigned int*)b - *(unsigned int*)c);
}
void merge_sort(int l, int r){
int m = (l + r) >> 1, i, j, k;
if (l == r) return;
merge_sort(l, m);
merge_sort(m + 1, r);
for (i=l, j=m+1, k=l; i<=m || j<=r; )
if (j > r || (i <= m && a[i] < a[j]))
b[k++] = a[i++];
else
b[k++] = a[j++];
for (k = l; k <= r; k++) a[k] = b[k];
}
void bin_src(){
int i, step;
for (step=1;step<=m;step<<=1);
for (i=0;step;step>>=1)
if (i+step<=m && a[i+step]<=k)
i+=step;
if (a[i]==k)
s++;
}
int main(){
int i;
char x;
FILE *fin=fopen("abc2.in","r");
L=0;
fscanf(fin,"%c",&v[++L]);
while (v[L]!='\n'){
v[L]-='a';
fscanf(fin,"%c",&v[++L]);
}
L--;
n=0;m=0;
fscanf(fin,"%c",&x);
while (x!='\n'){
n++;
x-='a';
a[m]=a[m]*3+x;
fscanf(fin,"%c",&x);
}
hash[a[m]%HASH]=1;
if (!feof(fin))
do{
m++;
for (i=1;i<=n;i++){
fscanf(fin,"%c",&x);
a[m]=a[m]*3+(x-'a');
}
hash[a[m]%HASH]=1;
fscanf(fin,"\n");
}
while (!feof(fin));
fclose(fin);
merge_sort(0,m);
k=v[1];ultim=1;
for (i=2;i<=n;i++){
k*=3;
k+=v[i];
ultim*=3;
}
bin_src();
for (i=n+1;i<=L;i++){
k-=ultim*v[i-n];
k*=3;
k+=v[i];
if (hash[k%HASH])
bin_src();
}
FILE *fout=fopen("abc2.out","w");
fprintf(fout,"%d\n",s);
fclose(fout);
return 0;
}