Cod sursa(job #2840643)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 28 ianuarie 2022 15:59:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int NMAX = 2e6 + 1;

int N, M;
char A[NMAX], B[NMAX], S[(NMAX << 1)];

int Z[(NMAX << 1)];

static inline void Read ()
{
    f.tie(nullptr);

    f >> (A + 1), N = (int)strlen(A + 1);
    f >> (B + 1), M = (int)strlen(B + 1);

    return;
}

static inline int my_min (int a, int b)
{
    return ((a < b) ? a : b);
}

static inline void ZFunction ()
{
    int L = 0, R = 0;

    Z[1] = N + M + 1;

    for(int i = 2; i <= N + M + 1; ++i)
    {
        if(i <= R)
            Z[i] = my_min(R - i + 1, Z[i - L + 1]);
        else
            Z[i] = 0;

        while(i + Z[i] <= N + M + 1 && S[i + Z[i]] == S[Z[i] + 1])
            ++Z[i];

        if(i + Z[i] - 1 >= R)
            L = i, R = i + Z[i] - 1;
    }

    return;
}

static inline void Build ()
{
    for(int i = 1; i <= N; ++i)
        S[i] = A[i];

    S[N + 1] = '#';

    for(int i = 1; i <= M; ++i)
        S[N + 1 + i] = B[i];

    ZFunction();

    return;
}

static inline void Write ()
{
    vector < int > _temp;

    for(int i = N + 2; i <= N + M + 1; ++i)
        if(Z[i] == N)
            _temp.push_back(i - N - 2);

    g << (int)_temp.size() << '\n';

    for(int i = 0; i < my_min((int)_temp.size(), 1000); ++i)
    {
        if(i > 0)
            g << ' ';

        g << _temp[i];
    }

    if(!_temp.empty())
        g << '\n';

    return;
}

int main()
{
    Read();

    Build();

    Write();

    return 0;
}