Cod sursa(job #355288)

Utilizator slayerdmeMihai Dumitrescu slayerdme Data 10 octombrie 2009 17:25:02
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.67 kb
#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;
}