Cod sursa(job #2117238)

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

#define SIZE 2000010
#define LIM 1000

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

            if (n == LIM) {
                break;
            }
        }
    }

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

    return 0;
}