Pagini recente » Cod sursa (job #94636) | Cod sursa (job #619015) | Cod sursa (job #2224559) | Cod sursa (job #1639817) | Cod sursa (job #355284)
Cod sursa(job #355284)
#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, na1;
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);
na1 = na + 1;
while (scanf("%c", &b[nb % na1]) != EOF && b[nb] != '\n') {
if (nb > na) {
hash = (hash - hashValue(b[(nb - na) % na1]) * hibase) * BASE + hashValue(b[nb % na1]);
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 < MAXPOS) {
positions[numberOfReps] = nb - na;
}
numberOfReps++;
// }
}
} else {
hash = hash * BASE + hashValue(b[nb]);
}
nb++;
}
printf("%d\n", numberOfReps);
if (numberOfReps > MAXPOS) {
numberOfReps = MAXPOS;
}
for (i = 0; i < numberOfReps; i++) {
printf("%d ", positions[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}