Cod sursa(job #2117228)

Utilizator 24601Dan Ban 24601 Data 28 ianuarie 2018 18:15:19
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <string.h>

#define SIZE 2000000

static char t[SIZE+1], p[SIZE+1];
static size_t pi[SIZE+1], s[SIZE+1];

int main(void)
{
    size_t i, k, plen, tlen, n = 0;

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

    scanf("%s %s", p + 1, t + 1);
    plen = strlen(p + 1);
    tlen = strlen(t + 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) {
            s[n] = i - plen;
            n++;
        }
    }

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

    return 0;
}