Pagini recente » Cod sursa (job #1214233) | Cod sursa (job #1889161) | Cod sursa (job #173396) | Cod sursa (job #1044406) | Cod sursa (job #355043)
Cod sursa(job #355043)
#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
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') {
//printf("testa[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);
//printf("aHash value: %d\n", aHash);
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;
}