Pagini recente » Cod sursa (job #76774) | Cod sursa (job #1488153)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define TXT_DIM 10000007
#define DIM 27
#define NMAX 50007
using namespace std;
char buff[TXT_DIM], tmp[DIM];
unsigned int v[NMAX], len, sze, pw[DIM], n, aux, ct, x;
void init()
{
pw[0] = 1;
for(int i = 1; i< 20; ++i) pw[i] = pw[i-1] * 3;
}
int cautbin(int value)
{
int step = 1<<16, first = 0, index;
for(;step; step>>=1)
{
index = first + step;
if(index <= n)
{
if(v[index] <= value)
{
first = index;
}
}
}
return first;
}
void solve()
{
for(int i = 1; i< len; ++i)
{
aux = aux*3 + (buff[i]-'a');
}
aux *=3;
for(int i = len; i<= sze; ++i)
{
aux += buff[i]-'a';
x = cautbin(aux);
//printf("aux = %d x = %d\n", aux, x);
if(v[x] == aux) ct++;
aux -= (buff[i-len+1]-'a')*pw[len-1];
aux *=3;
}
}
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
init();
scanf("%s", buff+1);
sze = strlen(buff+1);
for(int i =1; scanf("%s", tmp) == 1; ++i)
{
//printf("%s\n", tmp);
len = strlen(tmp);
for(int j = 1; j<= len; ++j)
{
v[i] = v[i]*3 + (tmp[j-1]-'a');
}
//printf("%d\n", v[i]);
n = i;
}
sort(v+1, v+n+1);
solve();
printf("%d\n", ct);
return 0;
}