Pagini recente » Cod sursa (job #276635) | Cod sursa (job #2257855) | Cod sursa (job #2491397) | Cod sursa (job #2403153) | Cod sursa (job #2379917)
#include <fstream>
#include <vector>
#include <set>
#include <string>
#define MOD1 4294959637
#define MOD2 4294967111
#define PRIM1 31
#define PRIM2 127
#define SZ 50021
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<ull, ull> HASH;
ui nr, szA, szB;
set < HASH > hashTable[SZ];
HASH hashed;
ull P1 = 1, P2 = 1, tempCalc1, tempCalc2;
string A, B;
int main()
{
ui i, pos;
f >> A;
szA = A.size();
while(f >> B){
szB = B.size();
hashed = {0, 0};
for(i=0; i<szB; ++i){
hashed.first = (((hashed.first << 5) - hashed.first) % MOD1 + B[i]) % MOD1;
hashed.second = (((hashed.second << 7) - hashed.second) % MOD2 + B[i]) % MOD2;
}
pos = (hashed.first + hashed.second) % SZ;
if(hashTable[pos].find(hashed) == hashTable[pos].end())
hashTable[pos].insert(hashed);
}
hashed = {0, 0};
for(i=0; i<szB; ++i){
hashed.first = (((hashed.first << 5) - hashed.first) % MOD1 + A[i]) % MOD1;
hashed.second = (((hashed.second << 7) - hashed.second) % MOD2 + A[i]) % MOD2;
if(i!=0){
P1 = ((P1 << 5) - P1) % MOD1;
P2 = ((P2 << 7) - P2) % MOD2;
}
}
pos = (hashed.first + hashed.second) % SZ;
if(hashTable[pos].find(hashed) != hashTable[pos].end())
++nr;
for(i=szB; i<szA; ++i){
tempCalc1 = (hashed.first - ((A[i - szB] * P1) % MOD1) + MOD1);
tempCalc2 = (hashed.second - ((A[i - szB] * P2) % MOD2) + MOD2);
hashed.first = (((tempCalc1 << 5) - tempCalc1) % MOD1 + A[i]) % MOD1;
hashed.second = (((tempCalc2 << 7) - tempCalc2) % MOD2 + A[i]) % MOD2;
pos = (hashed.first + hashed.second) % SZ;
if(hashTable[pos].find(hashed) != hashTable[pos].end())
++nr;
}
g << nr;
return 0;
}