Cod sursa(job #2181076)

Utilizator 24601Dan Ban 24601 Data 21 martie 2018 13:53:31
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.24 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 i, k, plen, tlen, n = 0, tst;
    ssize_t bsz;
    char *p, *t;

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

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

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

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

    return 0;
}