Cod sursa(job #282789)

Utilizator victorsbVictor Rusu victorsb Data 18 martie 2009 11:26:21
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>

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[MAX_N];

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) {
            S[++cnt] = i - N;
            k = P[k];
        }
    }
}

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

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