Pagini recente » Cod sursa (job #282181) | Cod sursa (job #1814649) | Cod sursa (job #358563) | Cod sursa (job #3132139) | Cod sursa (job #2379982)
#include <cstdio>
#include <cstring>
#include <vector>
#define NMAX 10000001
#define PRIM 3
#define SZ 50021
using namespace std;
typedef unsigned int ui;
ui nr, szA, szB;
char A[NMAX], B[21];
vector < ui > hashTable[SZ];
ui hashed, P = 1, tempCalc;
bool searchHash(ui h)
{
ui pos = h % SZ;
ui sz = hashTable[pos].size();
for(ui i=0; i<sz; ++i)
if(hashTable[pos][i] == h)
return true;
return false;
}
int main()
{
ui i;
freopen("abc2.in", "r", stdin);
freopen("abc2.out","w", stdout);
scanf("%s", A);
szA = strlen(A);
while(scanf("%s", B) != EOF){
szB = strlen(B);
hashed = 0;
for(i=0; i<szB; ++i)
hashed = (hashed << 1) + hashed + (B[i] - 'a');
if(!searchHash(hashed))
hashTable[hashed % SZ].push_back(hashed);
}
hashed = 0;
for(i=0; i<szB; ++i){
hashed = (hashed << 1) + hashed + (A[i] - 'a');
if(i!=0)
P = (P << 1) + P;
}
if(searchHash(hashed))
++nr;
for(i=szB; i<szA; ++i){
tempCalc = (hashed - ((A[i - szB] - 'a') * P));
hashed = (tempCalc << 1) + tempCalc + (A[i] - 'a');
if(searchHash(hashed))
++nr;
}
printf("%d\n", nr);
return 0;
}