Pagini recente » Cod sursa (job #2718295) | Cod sursa (job #2065692) | Cod sursa (job #907768) | Cod sursa (job #817944) | Cod sursa (job #1191631)
#include <fstream>
#include <cstring>
#include <string>
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, "%c", &v[0]);
for(i = 1; v[i-1] != '\n'; i++)
{
fscanf(in, "%c", &v[i]);
}
fscanf(in, "%c", &cuv[0]);
cuvL = 1;
for(i = 1; cuv[i-1] != '\n'; i++)
{
fscanf(in, "%c", &cuv[i]);
cuvL++;
}
cuvL--;
unsigned int r = transf();
add(r);
while(fscanf(in, "%c", &cuv[0]) != EOF)
{
for(i = 1; cuv[i-1] != '\n'; i++)
{
fscanf(in, "%c", &cuv[i]);
}
r = transf();
add(r);
}
for(i = 0; i < strlen(v)-cuvL; i++)
{
cmp(i);
}
fprintf(out,"%d", nrap);
return 0;
}