Pagini recente » Cod sursa (job #1966161) | Cod sursa (job #281980) | Cod sursa (job #196986) | Cod sursa (job #3039304) | Cod sursa (job #1191632)
#include <fstream>
#include <cstring>
using namespace std;
FILE* in = fopen("abc2.in", "r");
FILE* out = fopen("abc2.out", "w");
const int MAX_N = 50000, K = 666013, MAX_M = 10000000;
int lst[K], urm[MAX_N+1];
unsigned int val[MAX_N+1];
int nr, cuvL;
char v[MAX_M], cuv[20];
unsigned int nrap;
bool inline check(int x)
{
int p = lst[x&(K-1)];
while(p != 0 && val[p] != x)
{
p = urm[p];
}
return p != 0;
}
void inline del(int x)
{
int r = x&(K-1), p;
if(x == val[lst[r]])
{
lst[r] = urm[lst[r]];
return;
}
p = lst[r];
while(urm[p] != 0 && val[urm[p]] != x)
{
p = urm[p];
}
if(val[urm[p]] == x)
{
urm[p] = urm[urm[p]];
}
}
void inline add(int x)
{
if(!check(x))
{
int place = x&(K-1);
val[++nr] = x;
urm[nr] = lst[place];
lst[place] = nr;
}
}
unsigned int transf()
{
int p = 1;
unsigned int x = 0;
for(int i = 0; i < cuvL; i++)
{
x += p*(cuv[i]-'a');
p *= 3;
}
return x;
}
void cmp(int start)
{
for(int i = 0; i < cuvL; i++)
{
cuv[i] = v[start+i];
}
int x = transf();
if(check(x))
{
nrap++;
}
}
int main()
{
int i;
fscanf(in, "%s", v);
fscanf(in, "%s", cuv);
cuvL = strlen(cuv);
unsigned int r = transf();
add(r);
while(fscanf(in, "%s", &cuv[0]) != EOF)
{
r = transf();
add(r);
}
for(i = 0; i < strlen(v)-cuvL; i++)
{
cmp(i);
}
fprintf(out,"%d", nrap);
return 0;
}