Pagini recente » Cod sursa (job #1798803) | Cod sursa (job #2754677) | Cod sursa (job #846190) | Cod sursa (job #329388) | Cod sursa (job #101861)
Cod sursa(job #101861)
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <sstream>
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
using namespace std;
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define FORD(i, N, M) for (int i = (int)(N); i >= (int)(M); --i)
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define TIP(x) (cerr << #x << " = " << (x) << endl)
#define sz size()
#define pb push_back
#define mp make_pair
#define pf first
#define ps second
#define INF 1000000000
#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
typedef vector<int> VI;
typedef vector<string> VS;
typedef long long LL;
const int MAX_LEN = 10000010;
const uint HASH_SIZE = 1 << 20;
const int N_PRIMES = 2;
uint primes[N_PRIMES] = {3, 19};
int N;
char cuv[64];
char text[MAX_LEN];
bool viz[N_PRIMES][HASH_SIZE];
inline uint fun(uint val) {
return val & (HASH_SIZE - 1);
}
int main() {
freopen("abc2.in", "rt", stdin);
freopen("abc2.out", "wt", stdout);
fgets(text, MAX_LEN, stdin);
while (true) {
CLEAR(cuv);
fgets(cuv, 64, stdin);
int len = strlen(cuv);
if (cuv[len - 1] == '\n') {
cuv[len - 1] = 0;
--len;
}
if (len == 0) {
break;
}
N = len;
uint hash[N_PRIMES];
CLEAR(hash);
REP(d, N_PRIMES) {
for (int i = 0; i < len; ++i) {
hash[d] = hash[d] * primes[d] + cuv[i];
}
viz[d][fun(hash[d])] = 1;
}
}
uint crt_hash[N_PRIMES], primeN[N_PRIMES];
REP(d, N_PRIMES) crt_hash[d] = 0, primeN[d] = 1;
REP(d, N_PRIMES) {
for (int i = 0; i < N; ++i)
primeN[d] *= primes[d];
primeN[d] = fun(primeN[d]);
}
int i, sol = 0;
REP(d, N_PRIMES) {
for (i = 0; i < N; ++i) {
crt_hash[d] = crt_hash[d] * primes[d] + text[i];
}
crt_hash[d] = fun(crt_hash[d]);
}
for (; text[i] != '\0'; ++i) {
int cnt = 0;
REP(d, N_PRIMES) cnt += viz[d][crt_hash[d]];
sol += (int) (cnt == N_PRIMES);
REP(d, N_PRIMES) {
crt_hash[d] *= primes[d];
crt_hash[d] = crt_hash[d] + (HASH_SIZE - fun(primeN[d] * text[i - N]));
crt_hash[d] += text[i];
crt_hash[d] = fun(crt_hash[d]);
}
}
printf("%d\n", sol);
return 0;
}