Cod sursa(job #1797744)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 4 noiembrie 2016 18:39:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

#define DIM 2000006

char A[DIM], B[DIM];
vector <int> fail, rezultate;

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

    scanf("%s", A);
    scanf("%s", B);

    int N = strlen(A);

    fail.resize(N + 2);

    int j;
    fail[0] = j = -1;

    for(int i = 0; i < N; ++i) {
        while(j >= 0 && A[j] != A[i]) {
            j = fail[j];
        }
        ++j;
        fail[i + 1] = j;
    }

    j = 0;
    int M = strlen(B);
    int total = 0;
    rezultate.reserve(1002); // !
    for(int i = 0; i < M; ++i) {
        while(j >= 0 && A[j] != B[i]) {
            j = fail[j];
        }
        ++j;
        if(j == N) {
            ++total;
            if(total <= 1000) rezultate.push_back(i - N + 1);
            j = fail[j];
        }
    }

    cout << total << '\n';
    for(int i = 0; i < total && i < 1000; ++i) {
        cout << rezultate[i] << ' ';
    }

    cout << '\n';
    return 0;
}