Cod sursa(job #355307)

Utilizator slayerdmeMihai Dumitrescu slayerdme Data 10 octombrie 2009 18:04:03
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.32 kb
#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;
}