Pagini recente » Cod sursa (job #2920028) | Cod sursa (job #2261054) | Cod sursa (job #66312) | Cod sursa (job #2214323) | Cod sursa (job #940396)
Cod sursa(job #940396)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MOD 666013
#define MAXP 25
#define MAXL 10000010
using namespace std;
char sir[MAXL], cuv[MAXP];
int pow[MAXP];
vector < unsigned int > hash[MOD];
inline int search(unsigned int x)
{
unsigned int l = x % MOD;
vector < unsigned int>::iterator it;
for ( it = hash[l].begin(); it != hash[l].end(); it++)
{
if(*it == x)
return 1;
}
return 0;
}
inline void add(unsigned int x)
{
unsigned int l = x % MOD;
hash[l].push_back(x);
}
int main()
{
int N, M, i, b = 3, val, sol = 0;
pow[0] = 1;
for ( i = 1; i < MAXP; i++)
pow[i] = pow[i-1] * b;
FILE *fin = fopen("abc2.in", "r");
fgets(sir, 10000002, fin);
N = strlen(sir) - 2;
fgets(cuv, 22, fin);
M = strlen(cuv) - 2;
while(!feof(fin))
{
if(strlen(cuv) - 2 == M)
{
val = 0;
for ( i = 0; i <= M; i++)
val = val * b + (cuv[i] - 'a');
if(!search(val))
add(val);
}
fgets(cuv, 22, fin);
}
fclose(fin);
val = 0;
for ( i = 0; i <= M; i++)
{
val = val * b + (sir[i] - 'a');
}
sol += search(val);
for ( i = M+1; i <= N; i++)
{
val = (val - (sir[i-M-1] - 'a')*pow[M])*b + sir[i]-'a';
sol += search(val);
}
FILE *fout = fopen("abc2.out","w");
fprintf(fout, "%d\n", sol);
fclose(fout);
return 0;
}