Pagini recente » Cod sursa (job #486664) | Cod sursa (job #2447439) | Cod sursa (job #2761753) | Cod sursa (job #1048465) | Cod sursa (job #355307)
Cod sursa(job #355307)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 2000001
#define MAXDISP 1000
#define BASE 73
#define CHARDEC 48
#define hashValue(c) (((int) (c)) - CHARDEC)
int main() {
char a[MAXSIZE], b[MAXSIZE];
int na, nb, i, hibase = 1, repNumber = 0;
int match[MAXDISP];
int hash = 0, aHash = 0;
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). Overflow is OK since it then calculates mod 2^32
for (i = 0; i < na - 1; i++) {
hibase = hibase * BASE;
}
for (i = 0; i < na; i++) {
aHash = aHash * BASE + hashValue(a[i]);
hash = hash * BASE + hashValue(b[i]);
}
if (hash == aHash) {
match[repNumber] = 0;
repNumber++;
}
for (i = na; i < nb; i++) {
hash -= hashValue(b[i - na]) * hibase;
hash = hash * BASE + hashValue(b[i]);
if (hash == aHash) {
if (repNumber < MAXDISP) {
match[repNumber] = i - na + 1;
}
repNumber++;
}
}
printf("%d\n", repNumber);
if (repNumber > MAXDISP) {
repNumber = MAXDISP;
}
for (i = 0; i < repNumber; i++) {
printf("%d ", match[i]);
}
return 0;
}