Pagini recente » Cod sursa (job #2592699) | Cod sursa (job #2183097) | Cod sursa (job #142163) | Cod sursa (job #2182009) | Cod sursa (job #2379934)
#include <fstream>
#include <vector>
#include <set>
#include <string>
#define MOD 100021
#define PRIM 127
#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 << 7) - hashed) % MOD + B[i]) % MOD;
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 << 7) - hashed) % MOD + A[i]) % MOD;
if(i!=0)
P = ((P << 7) - P) % MOD;
}
pos = hashed % SZ;
if(hashTable[pos].find(hashed) != hashTable[pos].end())
++nr;
for(i=szB; i<szA; ++i){
tempCalc = (hashed - ((A[i - szB] * P) % MOD) + MOD);
hashed = (((tempCalc << 7) - tempCalc) % MOD + A[i]) % MOD;
pos = hashed % SZ;
if(hashTable[pos].find(hashed) != hashTable[pos].end())
++nr;
}
g << nr;
return 0;
}