Cod sursa(job #873224)

Utilizator Teodor94Teodor Plop Teodor94 Data 6 februarie 2013 23:01:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <cassert>
#include <cstring>

#define MAX_N 2000001
#define MAX_Q 1001

int n1, n2;
int nr, ans[MAX_Q];
int pi[MAX_N];
char s1[MAX_N], s2[MAX_N];

inline void pull(char A[], int n) {
    for (int i = n; i > 0; --i)
        A[i] = A[i - 1];

    A[0] = ' ';
}

inline int min(int x, int y) {
    return (x < y) ? x : y;
}

void make_prefix() {
    int q = 0;

    for (int i = 2; i <= n1; ++i) {
        while (q && s1[q + 1] != s1[i])
            q = pi[q];

        if (s1[q + 1] == s1[i])
            ++q;

        pi[i] = q;
    }
}

void write() {
    printf("%d\n", nr);

    for (int i = 1; i <= min(nr, 1000); ++i)
        printf("%d ", ans[i]);

    printf("\n");
}

int main() {
    assert(freopen("strmatch.in", "r", stdin));
    assert(freopen("strmatch.out", "w", stdout));

    gets(s1);
    gets(s2);

    n1 = strlen(s1);
    n2 = strlen(s2);

    pull(s1, n1);
    pull(s2, n2);

    make_prefix();

    int q = 0;

    for (int i = 1; i <= n2; ++i) {
        while (q && s1[q + 1] != s2[i])
            q = pi[q];

        if (s1[q + 1] == s2[i])
            ++q;

        if (q == n1) {
            q = pi[n1];

            ++nr;

            if (nr <= 1000)
                ans[nr] = i - n1;
        }
    }

    write();
}