Pagini recente » Cod sursa (job #2628684) | Cod sursa (job #1602996) | Cod sursa (job #1161642) | Cod sursa (job #560093) | Cod sursa (job #837504)
Cod sursa(job #837504)
#include <stdio.h>
#include <vector>
#include <string.h>
#define CMAX 10000002
#define NMAX 50000
#define LMAX 22
#define P 666013
using namespace std;
char cuv[CMAX];
vector <unsigned long> hash[P];
unsigned long harr;
long l, c;
long count;
unsigned long val(char *s)
{
long i;
unsigned long sol = 0;
unsigned long t = 1;
for (i = l - 1; i >= 0; i--)
{
sol += t * (s[i] - 'a');
t = t * 3;
}
return sol;
}
void read()
{
FILE *f = fopen("abc2.in", "r");
char s[LMAX];
unsigned long vall;
fgets(cuv, CMAX, f);
c = strlen(cuv) - 1;
cuv[c] = '\0';
fgets(s, LMAX, f);
l = strlen(s) - 1;
s[l] = '\0';
vall = val(s);
hash[vall % P].push_back(vall);
while (fgets(s, LMAX, f) != NULL)
{
s[l] = '\0';
vall = val(s);
hash[vall % P].push_back(vall);
}
fclose(f);
}
unsigned long calc_put()
{
int i;
unsigned long p = 1;
for (i = 1; i < l; i++)
p = p * 3;
return p;
}
int search_val(unsigned long vall)
{
int i, n = hash[vall % P].size();
for (i = 0; i < n; i++)
if (hash[vall % P][i] == vall)
return 1;
return 0;
}
void dostuff()
{
long i;
unsigned long vall = val(cuv), sval, eval;
if (search_val(vall))
count++;
harr = calc_put();
for (i = 1; i <= c - l; i++)
{
sval = (cuv[i - 1] - 'a') * harr;
eval = cuv[i + l - 1] - 'a';
vall = (vall - sval) * 3 + eval;
if (search_val(vall))
count++;
}
}
void print()
{
FILE *f = fopen("abc2.out", "w");
fprintf(f, "%ld", count);
fclose(f);
}
int main()
{
read();
dostuff();
print();
return 0;
}