Cod sursa(job #1446431)

Utilizator caen1c a e n caen1 Data 1 iunie 2015 20:32:37
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <math.h>
#include <string.h>

#define NMAX 2000005
#define MMAX 1000
#define MOD 104729

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

static size_t read(char *s, int lim)
{
    char *p;

    fgets(s, lim, stdin);
    if ((p = strchr(s, '\n')))
        *p = '\0';

    return strlen(s);
}

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 * 26 + s[i]) % MOD;

    return hh;
}

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);

    plen = read(Pattern, sizeof Pattern);
    tlen = read(Text, sizeof Text);
    h = (unsigned long long) pow(26, plen - 1) % MOD;

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

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

    for (i = 1; i <= tlen - plen; i++) {
        th = (26 * (th - Text[i - 1] * h) + 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;
}