Pagini recente » Borderou de evaluare (job #1650489) | Cod sursa (job #2366453) | Cod sursa (job #1843017) | Cod sursa (job #2678142) | Cod sursa (job #2379955)
#include <fstream>
#include <string>
#include <set>
#define PRIM 3
#define SZ 50021
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
typedef unsigned int ui;
ui nr, szA, szB;
string A, B;
set < ui > hashTable[SZ];
ui hashed, P = 1, tempCalc;
int main()
{
ui i, pos;
f >> A;
szA = A.size();
while(f >> B){
szB = B.size();
hashed = 0;
for(i=0; i<szB; ++i)
hashed = hashed * PRIM + (B[i] - 'a');
pos = hashed % SZ;
if(hashTable[pos].find(hashed) == hashTable[pos].end())
hashTable[pos].insert(hashed);
}
hashed = 0;
for(i=0; i<szB; ++i){
hashed = hashed * PRIM + (A[i] - 'a');
if(i!=0)
P = (P << 1) + P;
}
pos = hashed % SZ;
if(hashTable[pos].find(hashed) != hashTable[pos].end())
++nr;
for(i=szB; i<szA; ++i){
tempCalc = (hashed - ((A[i - szB] - 'a') * P));
hashed = (tempCalc << 1) + tempCalc + (A[i] - 'a');
pos = hashed % SZ;
if(hashTable[pos].find(hashed) != hashTable[pos].end())
++nr;
}
g << nr;
return 0;
}