Cod sursa(job #1448144)

Utilizator caen1c a e n caen1 Data 6 iunie 2015 12:50:41
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 4.29 kb
#include <math.h>
#include <stdio.h>
#include <string.h>

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

static int match[NMAX], /* trans[NMAX]['z' + 1], prefix[NMAX], Z[2 * NMAX + 1], */ BC['z' + 1][NMAX];
static char Text[NMAX], Pattern[NMAX], F[2 * NMAX + 1];

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 * P + 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(P, 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 = (P * (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(int k, int q, char ch)
{
    char aux[NMAX], *p;

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

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

static void build_automaton(size_t plen, int alphabet)
{
    size_t i;
    int 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(k, i, j));
            trans[i][j] = k + 1;
        }
}

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

    build_automaton(plen, 'z');

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

    return n;
}

static void build_prefix(size_t plen)
{
    size_t i;
    int 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)
{
    size_t i;
    int n = 0, k;

    build_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;
}

static int z_algorithm(size_t tlen, size_t plen)
{
    int L, R, n = 0;
    size_t i, j;

    strncpy(F, Pattern, sizeof F);
    strncat(F, Text, sizeof F - plen);

    L = R = 0;
    for (i = 0; i < tlen + plen; i++) {
        if (i > R) {
            L = R = i;
            while (R < tlen + plen && F[R - L] == F[R])
                R++;
            Z[i] = R - L;
            R--;
        } else {
            j = i - L;
            if (Z[j] < R - i + 1) {
                Z[i] = Z[j];
            } else {
                L = i;
                while (R < tlen + plen && F[R - L] == F[R])
                    R++;
                Z[i] = R - L;
                R--;
            }
        }

        if (Z[i] >= plen && i >= plen)
            match[n++] = i - plen;
    }

    return n;
}
*/

static void bad_char(size_t plen)
{
    int i, j;

    memset(BC, -1, sizeof BC);

    for (i = 1; i < plen; i++) {
        for (j = 0; j <= 'z'; j++)
            BC[j][i] = BC[j][i - 1];
        BC[Pattern[i - 1]][i] = i - 1;
    }
}

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

    bad_char(plen);

    for (i = plen - 1; i < tlen; ) {
        j = plen - 1;
        k = i;
        while (j >= 0 && Pattern[j] == Text[k]) {
            j--;
            k--;
        }

        if (j == -1) {
            match[n++] = k + 1;
            i++;
        } else {
            i += j - BC[Text[k]][j];
        }
    }

    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(boyer_moore(tlen, plen));

    return 0;
}