Pagini recente » Cod sursa (job #181366) | Cod sursa (job #3274485) | Cod sursa (job #2833005) | Cod sursa (job #1272724) | Cod sursa (job #2108295)
#include<iostream>
#include<fstream>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int N = 10000005;
long long char2number[256];
unordered_map<int, int> fcv;
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 = 1<<((WORD_LENGTH-1)*2);
}
long long crtPower = 1;
long long hash = 0;
for(int i=0; i<WORD_LENGTH; ++i)
{
hash += crtPower * char2number[s[i]];
crtPower *= 4;
}
return hash;
}
int validateHash(long long hash){
return fcv[hash] > 0;
}
int main()
{
int sol = 0;
char text[N];
char cuv[25];
init_char2number();
in.getline(text, N);
///cout<<text<<"\n";
while(in.getline(cuv, 25))
{
///cout<<cuv<<" "<<word2hash(cuv)<<"\n";
++fcv[word2hash(cuv)];
}
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;
}