Pagini recente » Cod sursa (job #1564707) | Cod sursa (job #2889548) | Cod sursa (job #2180616) | Cod sursa (job #2169965) | Cod sursa (job #101304)
Cod sursa(job #101304)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char w[10000000], c, s[20],*pp;
int x, i, nr, ind, lg;
unsigned int sol, r, v[50005], pt[21], cnt;
int cmp(const void*a, const void*b){
unsigned int x = *(unsigned int *)a, y = *(unsigned int*)b;
if (x < y) return -1;
if (x > y) return 1;
return 0;
}
int caut(unsigned int cnt){
int li = 0, ls = ind, x;
while (li <= ls){
x = (li+ls) / 2;
if (cnt == v[x])
return 1;
else
if (cnt < v[x])
ls = x-1;
else
li = x+1;
}
return 0;
}
int main()
{
freopen("abc2.in", "rt", stdin);
freopen("abc2.out", "wt", stdout);
fgets(w, 10000005, stdin);
pt[0] = 1;
for (i=1; i<=20; i++)
pt[i] = 3*pt[i-1];
ind = -1;
while (!feof(stdin)){
fgets(s, 25, stdin);
nr = strlen(s) - 1;
r = 0;
for (i=0; i<nr; i++){
x = s[i]-'a';
r += x*pt[nr-i-1];
}
v[++ind] = r;
}
qsort(v, ind+1, sizeof(v[0]), cmp);
//lg = strlen(w);
//lg --;
cnt = 0;
for (i=0; i<nr; i++){
//for(pp=w;*pp!='\n';++p){
x = w[i]-'a';
//x=*pp-'a';
cnt += pt[nr-i-1]*x;
}
if (caut(cnt))
sol ++;
//for (i=nr; i<lg; i++){
for(pp=w+nr;*pp!='\n';++pp){
//x = w[i]-'a';
x=*pp-'a';
//cnt = (cnt - pt[nr-1]*(w[i-nr]-'a')) * 3 + x;
cnt = (cnt - pt[nr-1]*(*(pp-nr)-'a')) * 3 + x;
/*
if (caut(cnt))
sol ++;
*/
sol+=caut(cnt);
}
printf("%u\n", sol);
fclose(stdin);
fclose(stdout);
return 0;
}