Cod sursa(job #1446508)

Utilizator caen1c a e n caen1 Data 2 iunie 2015 02:42:07
Problema Potrivirea sirurilor Scor 66
Compilator c Status done
Runda Arhiva educationala Marime 1.44 kb
#include <stdio.h>
#include <string.h>

#define NMAX 2000005
#define MMAX 1000
#define MOD 100007

static int match[NMAX];
static char Text[NMAX], Pattern[NMAX];

static unsigned long long hash(char *s, size_t len)
{
    unsigned long long hh = 0;
    unsigned long i;

    for (i = 0; i < len; i++)
        hh = (hh * 62 + s[i]) % MOD;

    return hh;
}

static unsigned long long pw(int base, int p)
{
    unsigned long long aux;

    if (p == 0)
        return 1;
    if (p == 1)
        return base % MOD;

    aux = pw(base, p >> 1) % MOD;
    if (p & 1)
        return (((aux * aux) % MOD) * base % MOD) % MOD;
    else
        return aux * aux % MOD;
}

int main(void)
{
    char *t = Text;
    unsigned long long ph, th, h;
    size_t tlen, plen, i;
    int N = 0;

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s %s", Pattern, Text);
    plen = strlen(Pattern);
    tlen = strlen(Text);
    h = (unsigned long long) pw(62, plen - 1) % MOD;

    ph = hash(Pattern, plen);
    th = hash(Text, plen);

    if (ph == th && !memcmp(Pattern, Text, plen))
        match[N++] = 0;

    for (i = 1; i <= tlen - plen; i++) {
        th = (62 * (th - Text[i - 1] * h % MOD + MOD) + Text[i + plen - 1]) % MOD;
        if (th == ph && !strncmp(t + i, Pattern, plen))
            match[N++] = i;
    }

    printf("%d\n", N);
    for (i = 0; i < N && i < MMAX; i++)
        printf("%d ", match[i]);
    printf("\n");

    return 0;
}