Cod sursa(job #1447568)

Utilizator caen1c a e n caen1 Data 4 iunie 2015 19:05:19
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 2.87 kb
#include <math.h>
#include <stdio.h>
#include <string.h>

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

static int match[NMAX], trans[NMAX][0x100], prefix[NMAX];
static char Text[NMAX], Pattern[NMAX];


static void print(int n)
{
    int i;

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

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

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

    return hh;
}

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

    h = (unsigned long long) pow(33, plen - 1) % MOD;

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

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

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

    return N;
}

static int suffix(const char *P, int k, int q, char ch)
{
    char aux[NMAX], *p;

    memset(aux, 0, sizeof aux);
    strncpy(aux, P, q);
    aux[strlen(aux)] = ch;

    p = aux;
    return !strncmp(P, p + q - k, k + 1);
}

static void make_automaton(const char *P, size_t plen, int alphabet)
{
    int i, j, k;

    for (i = 0; i <= plen; i++)
        for (j = 0; j < alphabet; j++) {
            k = (plen + 1 < i + 2) ? plen + 1 : i + 2;
            do --k; while (!suffix(P, k, i, j));
            trans[i][j] = k + 1;
        }
}

static int finite_automata(int tlen, int plen)
{
    int s, n, i;

    make_automaton(Pattern, plen, 'z'); /* 'z' for entire alphanum */ 

    for (s = i = 0; i < tlen; i++) {
        s = trans[s][Text[i]];
        if (s == plen)
            match[n++] = i + 1 - plen;
    }

    return n;
}

static void kmp_prefix(size_t plen)
{
    int i, k;

    prefix[0] = k = -1;
    for (i = 1; i < plen; i++) {
        while (k != -1 && Pattern[k + 1] != Pattern[i])
            k = prefix[k];
        if (Pattern[k + 1] == Pattern[i])
            k++;
        prefix[i] = k;
    }
}

static int kmp(size_t tlen, size_t plen)
{
    int i, n = 0, k;

    kmp_prefix(plen);

    k = -1;
    for (i = 0; i < tlen; i++) {
        while (k != -1 && Pattern[k + 1] != Text[i])
            k = prefix[k];
        if (Pattern[k + 1] == Text[i])
            k++;
        if (k == plen - 1)
            match[n++] = i - plen + 1;
    }

    return n;
}

int main(void)
{
    size_t tlen, plen;

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

    scanf("%s %s", Pattern, Text);
    plen = strlen(Pattern);
    tlen = strlen(Text);

    /* print(rabin_karp(tlen, plen)); */
    /* print(finite_automata(tlen, plen)); */
    print(kmp(tlen, plen));

    return 0;
}