Cod sursa(job #600613)

Utilizator SpiderManSimoiu Robert SpiderMan Data 2 iulie 2011 16:59:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
# include <cstdio>
# include <cstring>

const char *FIN = "strmatch.in", *FOU = "strmatch.out";
const int MAX = 2000005;

char A[MAX], B[MAX];
int S[1005], pi[MAX], N, M;

void prefix (void) {
    for (int i = 2, k = 0; i <= N; pi[i++] = k) {
        for (; k && A[k + 1] != A[i]; k = pi[k]);
        if (A[k + 1] == A[i]) ++k;
    }
}

int main (void) {
    freopen (FIN, "r", stdin);

    fgets (A + 1, MAX, stdin), N = strlen (A + 1) - 1;
    fgets (B + 1, MAX, stdin), M = strlen (B + 1) - 1;

    prefix ();

    for (int i = 1, q = 0; i <= M; ++i) {
        for (; q && A[q + 1] != B[i]; q = pi[q]);
        if (A[q + 1] == B[i]) ++q;
        if (q == N) q = pi[N], (++S[0] < 1001 ? S[S[0]] = i - N : 0);
    }
    freopen (FOU, "w", stdout);
    printf ("%d\n", S[0]);
    for (int i = 1; i <= S[0] && i <= 1000; ++i)
        printf ("%d ", S[i]);
}