Pagini recente » Cod sursa (job #2225319) | Cod sursa (job #1127743) | Cod sursa (job #2830871) | Cod sursa (job #313775) | Cod sursa (job #98870)
Cod sursa(job #98870)
#include <stdio.h>
#include <string.h>
using namespace std;
const int M = 10000000; // maximum message length
const int H = 1<<20; // hash size
const int HM = H - 1; // hash mask
const int P = 1009; // some prime
int msg[M]; // the message
unsigned hash[H]; // the dictionary
int uhash[H]; // used positions of the hash
int wlen; // word length
int mlen; // message length
inline int hv(unsigned w) {
return (w * P) & HM;
}
inline void put(unsigned w) {
//printf("put %d\n",w);
int h = hv(w);
while (uhash[h]&&hash[h]!=w) h = (h+1)&HM;
hash[h]=w;
uhash[h]=1;
}
inline int has(unsigned w) {
int h = hv(w);
while (uhash[h]) {
if (hash[h]==w) return 1;
h=(h+1)&HM;
}
return 0;
}
int main() {
int c; // some character
unsigned w; // some word
int i;
FILE* in = fopen("abc2.in", "r");
FILE* out = fopen("abc2.out", "w");
// read the raw text
while ((c = fgetc(in)) != '\n' && c != '\r') msg[mlen++] = c-'a';
// read the dictionary, set |wlen|, and prepare |hash|
while (1) {
w=0; // the last read word
while ((c = fgetc(in)) == '\n' || c == '\r');
if (c == EOF) break;
wlen=0;
do {
w = 3 * w + (c - 'a');
++wlen;
} while ((c=fgetc(in))!='\n'&&c!='\r');
put(w);
}
//printf("mlen=%d wlen=%d\n",mlen,wlen);
// scan the raw text and count occurrences
unsigned t; // 3^(wlen-1)
int r = 0; // the result
for (t = 1, i = 1; i < wlen; ++i) t*=3;
for (i = 0, w = 0; i < wlen - 1 && i < mlen; ++i) w = 3*w+msg[i];
while (i < mlen) {
w=3*(w-t*msg[i-wlen])+msg[i];
//printf("w=%d\n",w);
if (has(w)) ++r;
++i;
}
fprintf(out,"%d\n",r);
fclose(in); fclose(out);
}