Cod sursa(job #1448149)

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

#define NMAX 2000005
#define MMAX 1000

static int BC['z' + 1][NMAX] = {-1}, match[MMAX];
static char Pattern[NMAX], Text[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 void bad_char(size_t plen)
{
    int i, j;

    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) {
            if (n < MMAX)
                match[n] = k + 1;
            n++;
            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;
}