Cod sursa(job #355045)

Utilizator slayerdmeMihai Dumitrescu slayerdme Data 10 octombrie 2009 07:42:45
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.94 kb
#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;
    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);

    while (scanf("%c", &b[nb]) != EOF && b[nb] != '\n') {
        if (nb < na) {
            hash = hash * BASE + hashValue(b[nb]);
        } else {
            hash = hash - hashValue(b[nb - na]) * hibase;
            hash = hash * BASE + hashValue(b[nb]);
            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 < 1000) {
                        positions[numberOfReps] = nb - na;
                    }
                    numberOfReps++;
//                }
            }

        }
        nb++;
    }

    printf("%d\n", numberOfReps);
    if (numberOfReps > 1000) {
        numberOfReps = 1000;
    }
    for (i = 0; i < numberOfReps; i++) {
        printf("%d ", positions[i]);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}