Pagini recente » Cod sursa (job #408507) | Cod sursa (job #1629337) | Cod sursa (job #1087530) | Cod sursa (job #2843637) | Cod sursa (job #98596)
Cod sursa(job #98596)
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <iostream>
#include <ctime>
using namespace std;
#define REP(i, N) for (i = 0; i < (N); ++i)
#define REPV(i, a, b) for (i = (a); i <= (b); ++i)
#define REPD(i, N) for (i = (N)-1; i >= 0; --i)
#define REPVD(i, b, a) for (i = (b); i >= (a); --i)
#define REPIT(it, a) for (it = (a).begin(); it != (a).end(); ++it)
#define CLR(a) memset(a, 0, sizeof(a))
#define MSET(a, v) memset(a, v, sizeof(a))
#define CPY(dest, source) memcpy(dest, source, sizeof(source))
#define PB push_back
#define SZ(a) (int)(a).size()
#define ALL(a) ((a).begin(), (a).end())
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<string> VS;
const int MAXH = 1<<20;
const int MAXHM = MAXH - 1;
const int MAXSLOTS = 16;
int N, M, size[MAXH];
char buff[32];
LL * hash[MAXH];
const int MAXS = 10000020;
char str[MAXS];
int hashcode(LL num) {
//unsigned int h = 0;
//int i;
//REP(i, M) {
// h = ((h << 5) + h) + (num & 3);
// num >>= 2;
//}
return num & MAXHM;
//return h % MAXH;
//return num % MAXH;
}
int find(LL num) {
int ind = hashcode(num), i;
//vector<LL>& h = hash[ind];
//REP(i, SZ(h)) if (h[i] == num) return 1;
REP(i, size[ind]) if (hash[ind][i] == num) return 1;
return 0;
}
void puthash(LL num) {
int ind = hashcode(num);
if (!find(num)) {
if (!size[ind]) hash[ind] = new LL[MAXSLOTS];
assert(size[ind]+1 < MAXSLOTS);
hash[ind][size[ind]++] = num;
//hash[ind].PB(num);
}
}
LL encode() {
M = strlen(buff);
LL res = 0;
int i;
//REP(i, M) res = (res << 2) | (buff[i] - 'a');
REP(i, M) res += res + res + buff[i] - 'a';
return res;
}
void parsewords() {
scanf("%s", str);
while (scanf("%s", buff) == 1) {
puthash(encode());
N++;
}
}
int main() {
time_t start = clock();
freopen("abc2.in", "rt", stdin);
freopen("abc2.out", "wt", stdout);
//random_shuffle(primes, primes + (sizeof(primes) / sizeof(primes[0])));
parsewords();
int S = strlen(str);
if (S < M) {
printf("0\n");
return 0;
}
int i;
//REP(i, MAXH) if (SZ(hash[i]) > 16) fprintf(stderr, "%d ", SZ(hash[i]));
//LL mask = 0;
//REP(i, M) mask = (mask << 2) | 3;
strncpy(buff, str, M);
LL curr = encode();
LL pw = 1;
REP(i, M-1) pw *= 3;
int res = find(curr);
REPV(i, M, S-1) {
//curr = (curr << 2) | (str[i] - 'a');
//curr &= mask;
if (str[i-M] == 'b') curr -= pw;
else if (str[i-M] == 'c') curr -= pw<<1;
curr += curr + curr + str[i] - 'a';
res += find(curr);
}
printf("%d\n", res);
fprintf(stderr, "%lf\n", 1.0 * (clock() - start) / CLK_TCK);
return 0;
}