Cod sursa(job #283542)

Utilizator gggbbbyyyDarkMan gggbbbyyy Data 19 martie 2009 11:57:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX_N 2000015

int N, M, cnt;
char A[MAX_N], B[MAX_N];
int P[MAX_N];
int S[1024];

void read() {
    scanf("%s", A);
    N = strlen(A);
    scanf("%s", B);
    M = strlen(B);
}

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

void kmp() {
    int k = 0;
    for (int i = 1; i <= M; ++i) {
        while (k > 0 && B[i - 1] != A[k])
            k = P[k];
        if (B[i - 1] == A[k])
            ++k;
        if (k == N) {
            ++cnt;
            if (cnt <= 1000)
                S[cnt] = i - N;
            k = P[k];
        }
    }
}

void solve() {
    prefix();
    kmp();
    printf("%d\n", cnt);
    for (int i = 1; i <= min(cnt, 1000); ++i)
        printf("%d ", S[i]);
    printf("\n");
}

int main() {
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    read();
    solve();
    return 0;
}