Pagini recente » Cod sursa (job #1719176) | Cod sursa (job #756931) | Cod sursa (job #323618) | Cod sursa (job #2479064) | Cod sursa (job #2901436)
#include <fstream>
#include <cstring>
#include <stdlib.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
char s[10000005];
#define prim 9983
char cuv[22];
int main()
{
fin >> s;
fin >> cuv;
unsigned int nr = 0, i, n = strlen(s), nc = strlen(cuv), putere = 1, j;
for (i = 0; i < nc; i++)
{
nr += (cuv[i] - 'a') * putere;
putere *= 3;
}
unsigned int loc = nr % prim;
unsigned int** h = (unsigned int**)malloc(prim * sizeof(unsigned int*));
unsigned int* ap = (unsigned int*)calloc(prim, sizeof(unsigned int));
ap[loc]++;
h[loc] = (unsigned int*)realloc(h[loc], ap[loc] * sizeof(unsigned int));
h[loc][ap[loc] - 1] = nr;
while (fin >> cuv)
{
nr = 0, putere = 1;
for (i = 0; i < nc; i++)
{
nr += (cuv[i] - 'a') * putere;
putere *= 3;
}
loc = nr % prim;
ap[loc]++;
h[loc] = (unsigned int*)realloc(h[loc], ap[loc] * sizeof(unsigned int));
h[loc][ap[loc] - 1] = nr;
}
int sol = 0;
nr = 0, putere = 1;
for (i = 0; i < nc; i++)
{
nr += (s[i] - 'a') * putere;
putere *= 3;
}
putere /= 3;
loc = nr % prim;
for (i = 0; i < ap[loc]; i++)
if (h[loc][i] == nr) { sol++; break; }
for (i = nc; i < n; i++)
{
nr -= s[i - nc] - 'a';
nr /= 3;
nr += (s[i] - 'a') * putere;
loc = nr % prim;
for (j = 0; j < ap[loc]; j++)
if (h[loc][j] == nr) { sol++; break; }
}
fout << sol;
return 0;
}