Pagini recente » Cod sursa (job #396751) | Cod sursa (job #1761228) | Cod sursa (job #1801448) | Cod sursa (job #1830896) | Cod sursa (job #355288)
Cod sursa(job #355288)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define MAXSIZE 2000000
#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, nb, 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);
scanf("%s %s", a, b);
na = strlen(a);
nb = strlen(b);
// 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;
}
for (i = 0; i < na; i++) {
aHash = aHash * BASE + hashValue(a[i]);
}
for (i = 0; i < na; i++) {
hash = hash * BASE + hashValue(b[i]);
}
if (hash == aHash) {
if (numberOfReps < MAXPOS) {
positions[numberOfReps] = 0;
}
numberOfReps++;
}
for (i = na; i < nb; i++) {
hash = hash - hashValue(b[i - na]) * hibase;
hash = hash * BASE + hashValue(b[i]);
if (hash == aHash) {
if (numberOfReps < MAXPOS) {
positions[numberOfReps] = i - na + 1;
}
numberOfReps++;
}
}
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;
}