Cod sursa(job #2325746)

Utilizator manciu_ionIon Manciu manciu_ion Data 22 ianuarie 2019 21:39:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstring>

#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005

using namespace std;

int M, N;
char A[NMax], B[NMax];
int pi[NMax], pos[1024];

ifstream in("strmatch.in");
ofstream out("strmatch.out");

void make_prefix()
{
    int i, q = 0;

    for (i = 1, pi[0] = 0; i < M; ++i)
    {
        while ((q > 0) and (A[q] != A[i]))
            q = pi[q - 1];
        if (A[q] == A[i])
            ++q;
        pi[i] = q;
    }
}

int main(void)
{
    int i, q = 0, n = 0;

    in >> A; //cout << A << '\n';
    in >> B; //cout << B << '\n';

    M = strlen(A);
    N = strlen(B);

    make_prefix();

    for (i = 0; i < N; ++i)
    {
        while ((q > 0) and (A[q] != B[i]))
            q = pi[q - 1];
        if (A[q] == B[i])
            ++q;
        if (q == M)
        {
            q = pi[q - 1];
            ++n;
            if (n <= 1000)
                pos[n] = i - M + 1;
        }
    }

    out << n << '\n';
    for (i = 1; i <= minim(n, 1000); ++i)
        out << pos[i] << " ";
    out << '\n';

    return 0;
}