Pagini recente » Monitorul de evaluare | Profil Duxar | Monitorul de evaluare | Cod sursa (job #534868) | Cod sursa (job #2108328)
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int N = 10000005;
const int MOD = 3420839;
char text[N];
struct hashul{
long long val;
hashul *next;
};
long long char2number[256];
hashul *(fcv[MOD]);
long long BIGGEST_POWER;
int WORD_LENGTH;
void init_char2number(){
char2number['a'] = 1;
char2number['b'] = 2;
char2number['c'] = 3;
}
long long word2hash(char *s){
if(!WORD_LENGTH)
{
WORD_LENGTH = strlen(s);
BIGGEST_POWER = 1LL<<((WORD_LENGTH-1)*2);
}
long long crtPower = 1;
long long hej = 0;
for(int i=0; i<WORD_LENGTH; ++i)
{
hej += crtPower * char2number[s[i]];
crtPower *= 4;
}
return hej;
}
int validateHash(long long hej){
hashul *p = fcv[hej%MOD];
while(p != NULL)
{
if(p->val == hej)
return 1;
p = p->next;
}
return 0;
}
int main()
{
int sol = 0;
char cuv[25];
init_char2number();
in.getline(text, N);
///cout<<text<<"\n";
while(in.getline(cuv, 25))
{
///cout<<cuv<<" "<<word2hash(cuv)<<"\n";
hashul *crtHash = new hashul;
crtHash->val = word2hash(cuv);
crtHash->next = fcv[crtHash->val % MOD];
fcv[crtHash->val % MOD] = crtHash;
}
long long crtHash = word2hash(text);
///cout<<"crtHash = "<<crtHash<<"\n";
sol += validateHash(crtHash);
for(int i=WORD_LENGTH; i < strlen(text); ++i)
{
crtHash = (crtHash / 4 + BIGGEST_POWER * char2number[text[i]]);
///for(int j=i - WORD_LENGTH + 1; j <= i; ++j) cout<<text[j]; cout<<" | crtHash = "<<crtHash<<"\n";
sol += validateHash(crtHash);
}
///cout<<"sol = "<<sol;
out<<sol;
return 0;
}