Pagini recente » Cod sursa (job #2209254) | Cod sursa (job #2405673) | Cod sursa (job #819751) | Cod sursa (job #2460537) | Cod sursa (job #1488308)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 666013;
const int MAX_WORDS = 50000;
const int MAX_LEN = 10000000;
const int MAX_WORDLEN = 20;
const int NIL = -1;
const int POW3[] = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467 };
char a[MAX_LEN + 1];
char word[MAX_WORDLEN + 1];
struct cell
{
unsigned key;
int next;
};
cell l[MAX_WORDS];
int ptr;
int H[MOD];
inline void hashInsert(const unsigned &key)
{
l[ptr].key = key;
l[ptr].next = H[key % MOD];
H[key % MOD] = ptr++;
}
inline bool hashFind(const unsigned &key)
{
int i = H[key % MOD];
while ((i != NIL) && (l[i].key != key))
i = l[i].next;
return i != NIL;
}
int main()
{
ifstream in("abc2.in");
ofstream out("abc2.out");
int n, i;
int res;
unsigned h;
in >> a;
memset(H, NIL, sizeof(H));
while (in >> word)
{
h = 0;
for (char *p = word; *p; p++)
h = ((h << 1) + h) + (*p - 'a');
if (!hashFind(h))
hashInsert(h);
}
in.close();
n = strlen(word);
i = 0;
h = 0;
res = 0;
while ((i < n) && (a[i] != '\0'))
{
h = ((h << 1) + h) + a[i] - 'a';
i++;
}
if (i == n)
{
res += hashFind(h);
while (a[i] != '\0')
{
h -= (a[i - n] - 'a') * POW3[n - 1];
h = ((h << 1) + h) + (a[i] - 'a');
res += hashFind(h);
i++;
}
}
out << res << '\n';
return 0;
}