Pagini recente » Cod sursa (job #1305165) | Cod sursa (job #2029954) | Cod sursa (job #614564) | Cod sursa (job #91725) | Cod sursa (job #355045)
Cod sursa(job #355045)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MAXSIZE 2000001
#define MAXDISPLAY 1000
#define BASE 79
#define BIGBASE 101
#define CHARDEC 48
#define MAXPOS 1000
#define hashValue(c) (((int) (c)) - CHARDEC)
//int hashValue(char c) {
// return ((int) c) - CHARDEC;
//}
int main() {
char a[MAXSIZE], b[MAXSIZE];
int na = 1, nb = 1, i, hibase, numberOfReps = 0;
int positions[MAXPOS];
int hash = 0, aHash = 0;
int notEqual;
freopen("strmatch.in", "r", stdin);
//freopen("strmatch.out", "w", stdout);
while (scanf("%c", &a[na]) != EOF && a[na] != '\n') {
aHash = aHash * BASE + hashValue(a[na]);
na++;
}
na--;
// Compute BASE ^ (na - 1). I don't care about overflow since it ends up being "mod 2^32"
hibase = 1;
for (i = 0; i < na - 1; i++) {
hibase = (hibase * BASE);
}
b[0] = (char) CHARDEC;
//assert(hashValue(b[0]) == 0);
while (scanf("%c", &b[nb]) != EOF && b[nb] != '\n') {
if (nb < na) {
hash = hash * BASE + hashValue(b[nb]);
} else {
hash = hash - hashValue(b[nb - na]) * hibase;
hash = hash * BASE + hashValue(b[nb]);
if (hash == aHash) {
// notEqual = 0;
// for (i = 1; i <= na; i++) {
// if (a[i] != b[nb - na + i]) {
// notEqual = 1;
// break;
// }
// }
// if (!notEqual) {
if (numberOfReps < 1000) {
positions[numberOfReps] = nb - na;
}
numberOfReps++;
// }
}
}
nb++;
}
printf("%d\n", numberOfReps);
if (numberOfReps > 1000) {
numberOfReps = 1000;
}
for (i = 0; i < numberOfReps; i++) {
printf("%d ", positions[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}