Cod sursa(job #2181500)

Utilizator 24601Dan Ban 24601 Data 21 martie 2018 18:29:34
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.37 kb
#include <stdio.h>
#include <string.h>
#include <unistd.h>

#define CHUNK (1 << 22)
#define SIZE 2000000
#define LIM 1000

static char buf[CHUNK];
static size_t pi[SIZE+1], s[LIM];

int main(void)
{
    size_t bsz, i, k, plen, tlen, n = 0, tst;
    char *p, *t;

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

    bsz = (size_t) read(0, buf, CHUNK);
    for (plen = 0; buf[plen] != '\n'; plen++)
        ;
    tst = plen + 1;
    tlen = bsz - tst;
    p = buf - 1;
    t = buf + tst - 1;

    if (plen + 1 == tlen) {
        if (memcmp(p + 1, t + 1, plen)) {
            puts("0");
        } else {
            puts("1\n0");
        }

        return 0;
    }

    pi[1] = 0;
    k = 0;
    for (i = 2; i <= plen; i++) {
        while (k > 0 && p[k + 1] != p[i]) {
            k = pi[k];
        }

        if (p[k + 1] == p[i]) {
            k++;
        }

        pi[i] = k;
    }

    k = 0;
    for (i = 1; i <= tlen; i++) {
        while (k > 0 && p[k + 1] != t[i]) {
            k = pi[k];
        }

        if (p[k + 1] == t[i]) {
            k++;
        }

        if (k == plen) {
            if (n < LIM) {
                s[n] = i - plen;
            }

            n++;
        }
    }

    printf("%lu\n", n);
    for (i = 0; i < (n < LIM ? n : LIM); i++) {
        printf("%lu%c", s[i], " \n"[i == (n < LIM ? n : LIM)]);
    }

    return 0;
}