Pagini recente » Cod sursa (job #1587006) | Cod sursa (job #837871) | Cod sursa (job #1616340) | Cod sursa (job #2839775) | Cod sursa (job #102996)
Cod sursa(job #102996)
#include <stdio.h>
#include <stdlib.h>
#define L_MAX 10000001
#define M_MAX 50001
char v[L_MAX];
long long a[M_MAX],b[M_MAX],k,ultim;
int L,m,n,s;
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);
}
if (!feof(fin))
do{
m++;
for (i=1;i<=n;i++){
fscanf(fin,"%c",&x);
a[m]=a[m]*3+(x-'a');
}
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];
bin_src();
}
FILE *fout=fopen("abc2.out","w");
fprintf(fout,"%d\n",s);
fclose(fout);
return 0;
}